Thursday, June 2, 2016

ModSecurity Failed Deleting Collection

Houston, we have a problem.  Looking at my ModSecurity audit log, I found quite a few log entries similar to the following (I have obfuscated the actual IP address for privacy reason):

Failed deleting collection (name "ip", key “X.X.X.X_"): Internal error

I was concerned that if the collection file was not being cleaned up automatically by Apache or ModSecurity, the file may grow to an astronomical size over time causing other problems.  While I wasn't able to find a definitive cause for the error by searching online, I stumbled upon 3 proposed workaround solutions:
  1. Use memcache for collections
  2. Set SecCollectionTimeout to a small value such as 600 (default is 3600 seconds)
  3. Install and run modsec-sdbm-util in a separate process to clean up the collection file regularly
Option 1 requires ModSecurity 3.0 or git-clone the memcache_collections branch, a choice I didn't want to make hastily.  There are reports that option 2 may not always work for everybody.  Just to be on the safe side, I implemented option 3 in addition to option 2.

For the record, I took the steps below to install modsec-sdbm-util on Amazon Linux AMI running Apache 2.4 with ModSecurity 2.8.

First, install all pre-requisite libraries and tools:

sudo su
yum install libtool autoreconf autoheader automake autoconf apr-util-devel

Then, download and install modsec-sdbm-util to a directory.

git clone https://github.com/SpiderLabs/modsec-sdbm-util.git
cd modsec-sdbm-util
./autogen.sh
./configure
make install

Check that it’s installed successfully by running (assuming ip.pag file is in /tmp):

/usr/local/modsecurity/bin/modsec-sdbm-util -s /tmp/ip.pag

If everything is okay, it should output a status report similar to:

Opening file: /tmp/ip.pag
Database ready to be used.
 [|] 10 records so far.
Total of 17 elements processed.
0 elements removed.
Expired elements: 7, inconsistent items: 0
Fragmentation rate: 41.18% of the database is/was dirty data.

Set up a cron job to run modsec-sdbm-util every half hour or so to remove expired elements from the collection file.

*/30 * * * *  /usr/local/modsecurity/bin/modsec-sdbm-util -k /tmp/ip.pag &> /dev/null

This should do it!  (Cross my fingers.)

Friday, May 27, 2016

ModSecurity Anti-Automation Rule Set for Detecting Denial of Service (DOS) Attacks, Part 2

Continuing my experiment with ModSecurity on a web server running in detection mode, I was discovering that a few of my users were triggering false alarms by the anti-DOS rules even though their number of submitted requests is well below the specified burst threshold of 100 requests per minute.  While searching online for a solution, I found that I was not the only one encountering this issue.  It seems that the false alarm occurs whenever web requests are submitted concurrently to the server by a user.  If the requests are submitted sequentially, the rules work as expected.  Unfortunately, I didn't find anybody posting a fix to the rules and so I took a trip through the tunnel...


Race Condition


The crux of the problem seems to be rule 981048:

#
#
# Check DOS Counter
# If the request count is greater than or equal to user settings, we then set the burst counter
# 
SecRule IP:DOS_COUNTER "@ge %{tx.dos_counter_threshold}" "phase:5,id:'981048',t:none,nolog,pass,setvar:ip.dos_burst_counter=+1,expirevar:ip.dos_burst_counter=%{tx.dos_burst_time_slice},setvar:!ip.dos_counter"


The rule does not operate atomically so rule operations such as unset(ip.dos_counter) are not guaranteed to finish first before the rule is executed by another request.  Consequently, when multiple concurrent requests activate the rule at the same time with the rule condition met, ip.dos_burst_counter is incremented by one for each concurrent request instead of incremented by one for all concurrent requests.  This means ip.dos_burst_counter can jump from 0 to ≥ 2.  Erroneously, the following rule 981049 then blocks the user because ip.dos_burst_counter is ≥ 2.

To illustrate with an example, a user has sent 99 requests slowly and regularly over time, so ip.dos_counter is now at 99 while ip.dos_burst_counter is 0.  All of the sudden, he sends 2 requests simultaneously.  Because the rule is not atomic, ip.dos_burst_counter is incremented twice and is now set to 2.  Had the 2 requests arrived sequentially, ip.dos_burst_counter would be 1 because ip.dos_counter would have been unset properly after the first request.  Now, because ip.dos_burst_counter is 2, the user is blocked even though he had not burst-ed.


The Solution


To fix the problem, I propose replacing rule 981048 with two chained rules to ensure ip.dos_burst_counter doesn't skip from 0 to ≥ 2.

#
# Check DOS Counter (Tick)
# If the request count is greater than or equal to user settings, we then set the burst counter to 1 if it's 0
# 
SecRule IP:DOS_COUNTER "@ge %{tx.dos_counter_threshold}" "chain,phase:5,id:'981048',t:none,nolog,pass"
SecRule &IP:DOS_BURST_COUNTER "@eq 0" "setvar:ip.dos_burst_counter=1,expirevar:ip.dos_burst_counter=%{tx.dos_burst_time_slice},setvar:!ip.dos_counter"

#
# Check DOS Counter (Tock)
# If the request count is greater than or equal to user settings, we then set the burst counter to 2 if it's 1
# 
SecRule IP:DOS_COUNTER "@ge %{tx.dos_counter_threshold}" "chain,phase:5,id:'981050',t:none,nolog,pass"
SecRule &IP:DOS_BURST_COUNTER "@ge 1" "setvar:ip.dos_burst_counter=2,expirevar:ip.dos_burst_counter=%{tx.dos_burst_time_slice},setvar:!ip.dos_counter"


For the previous example, the "tick" rule ensures ip.dos_burst_counter is set to at most 1 even if the rule is executed concurrently.  The "tock" rule dictates the condition that ip.dos_burst_counter can only be set to 2 if it was previously set to 1.  Together, the rules simulate the operation of the original rule while able to handle concurrency without triggering false positives. As for false negatives, the rules may trigger slightly later than the specified threshold crossing (e.g. 100 requests per minute) for concurrent requests due to the inherit lack of atomicity in ModSecurity.

Friday, May 20, 2016

ModSecurity Anti-Automation Rule Set for Detecting Denial of Service (DOS) Attacks, Part 1

In a previous article, I introduced ModSecurity as an effective web application firewall.  One of the things I like about ModSecurity is that it comes with a set of core rules (CRS) for detecting and handling various nefarious web activities like XSS and SQL injection.  I was thrilled to learn that CRS also comes with a set of rules for detecting DOS attacks.  I was curious to learn how the anti-DOS rules work.  I have stared at them long enough now that I'm beginning to see the light at the end of the tunnel.  In this article, I'll give an overview of how the DOS rules work.  In the next article, I'll dive a bit deeper by patching a race condition bug in the rules.

For reference, here are the rules from modsecurity_crs_11_dos_protection.conf:

#
# Anti-Automation rule set for detecting Denial of Service Attacks. 
#
#
# Enforce an existing IP address block and log only 1-time/minute
# We don't want to get flooded by alerts during an attack or scan so
# we are only triggering an alert once/minute.  You can adjust how often
# you want to receive status alerts by changing the expirevar setting below.
#
SecRule IP:DOS_BLOCK "@eq 1" "chain,phase:1,id:'981044',drop,msg:'Denial of Service (DoS) Attack Identified from %{tx.real_ip} (%{tx.dos_block_counter} hits since last alert)',setvar:ip.dos_block_counter=+1"
SecRule &IP:DOS_BLOCK_FLAG "@eq 0" "setvar:ip.dos_block_flag=1,expirevar:ip.dos_block_flag=60,setvar:tx.dos_block_counter=%{ip.dos_block_counter},setvar:ip.dos_block_counter=0"

#
# Block and track # of requests but don't log
SecRule IP:DOS_BLOCK "@eq 1" "phase:1,id:'981045',t:none,drop,nolog,setvar:ip.dos_block_counter=+1"

#
# skipAfter Check
# There are different scenarios where we don't want to do checks -
# 1. If the current IP address has already been blocked due to high requests
# In this case, we skip doing the request counts.
#
SecRule IP:DOS_BLOCK "@eq 1" "phase:5,id:'981046',t:none,nolog,pass,skipAfter:END_DOS_PROTECTION_CHECKS"

#
# DOS Counter
# Count the number of requests to non-static resoures
# 
SecRule REQUEST_BASENAME "!\.(jpe?g|png|gif|js|css|ico)$" "phase:5,id:'981047',t:none,nolog,pass,setvar:ip.dos_counter=+1"

#
# Check DOS Counter
# If the request count is greater than or equal to user settings,
# we then set the burst counter
# 
SecRule IP:DOS_COUNTER "@gt %{tx.dos_counter_threshold}" "phase:5,id:'981048',t:none,nolog,pass,t:none,setvar:ip.dos_burst_counter=+1,expirevar:ip.dos_burst_counter=%{tx.dos_burst_time_slice},setvar:!ip.dos_counter"

#
# Check DOS Burst Counter and set Block
# Check the burst counter - if greater than or equal to 2, then we set the IP
# block variable for 5 mins and issue an alert.
#
SecRule IP:DOS_BURST_COUNTER "@ge 2" "phase:5,id:'981049',t:none,log,pass,msg:'Potential Denial of Service (DoS) Attack from %{tx.real_ip} - # of Request Bursts: %{ip.dos_burst_counter}',setvar:ip.dos_block=1,expirevar:ip.dos_block=%{tx.dos_block_timeout}"

SecMarker END_DOS_PROTECTION_CHECKS


You can tailor the burst detection patterns by editing the file at /etc/httpd/modsecurity.d/modsecurity_localrules.conf:

#
# -- [[ DoS Protection ]] ----------------------------------------------------------------
#
# If you are using the DoS Protection rule set, then uncomment the following
# lines and set the following variables:
# - Burst Time Slice Interval: time interval window to monitor for bursts
# - Request Threshold: request # threshold to trigger a burst
# - Block Period: temporary block timeout
#
SecAction \
  "id:'900015', \
  phase:1, \
  t:none, \
  setvar:'tx.dos_burst_time_slice=60', \
  setvar:'tx.dos_counter_threshold=100', \
  setvar:'tx.dos_block_timeout=600', \
  nolog, \
  pass"

The anti-DOS rules count the number of requests for non-static resources made by an IP address.  By default, if the count exceeds 100 requests / minute, then the IP address is blocked for 10 minutes.  During the block period, any requests made by the IP address are dropped.  The counter starts afresh when the block period expires.  For reporting, the IP address is logged when it has just been blocked.  During the block period, the number of new requests by the IP address is logged every minute.

To implement this logic, the rules use 5 internal variables.  The dos_counter variable counts the number of requests during the time when client is not blocked.  In pseudo-code, the variable with its default value is:

dos_counter = 0

The dos_block_counter variable counts the number of requests during the time when client is blocked:

dos_block_counter = 0

The dos_burst_counter variable keeps track if a burst had occurred (whenever value is 2).  The value resets to 0 upon expiration time.

struct dos_burst_counter
    value = 0
    expiration = +inf

The dos_block variable indicates if an address is currently blocked (whenever value is 1).  The value resets to 0 upon expiration time.

struct dos_block
    value = 0
    expiration = +inf

The dos_block_flag variable controls the frequency of log updates during block period.  The value resets to 0 upon expiration time.

struct dos_block_flag
    value = 0
    expiration = +inf

The burst detection pattern is set with the 3 parameters:

DOS_COUNTER_THRESHOLD = 100
DOS_BURST_TIME_SLICE = 60
DOS_BLOCK_TIMEOUT = 600

In pseudo-code, the 6 anti-DOS rules are encapsulated in a function:

function process(request, response)
    //
    // Rule 981044 - log new requests by the blocked IP address every minute
    //
    if dos_block.value == 1 && dos_block_flag.value == 0
        dos_block_flag.value = 1
        dos_block_flag.expiration = unix_time() + 60
        print("DOS attack from %s %d hits since last alert", request.ip, dos_block_counter)
        dos_block_counter = 0

    //
    // Rule 982045 - drop request if IP address is blocked
    //
    if dos_block.value == 1
        dos_block_counter++
        response.drop()

    //
    // Rule 981046 - skip the following rules
    //
    if dos_block.value == 1
        return

    //
    // Rule 981047 - increment request counter
    //
    if request.non_static_resource
        dos_counter++

    //
    // Rule 981048 - check request counter against threshold
    //
    if dos_counter > DOS_COUNTER_THRESHOLD
        dos_burst_counter.value++
        dos_burst_counter.expiration = unix_time() + DOS_BURST_TIME_SLICE
        dos_counter = 0

    //
    // Rule 981049 - check if a burst had occurred
    //
    if dos_burst_counter.value >= 2
        dos_block.value = 1
        dos_block.expiration = unix_time() + DOS_BLOCK_TIMEOUT
        print("Potential DOS attack from %s - %d bursts, request.ip, dos_burst_counter.value)

Every time a web request comes in, the process() function is invoked.  In addition, every second or less, a background process calls the following function to reset any variables with pending expiration.

function expire()
    int time_now = unix_time()

    if time_now >= dos_block.expiration
        dos_block.value = 0
        dos_block.expiration = +inf

    if time_now >= dos_burst_counter.expiration
        dos_burst_counter.value = 0
        dos_burst_counter.expiration = +inf

    if time_now >= dos_block_flag.expiration
        dos_block_flag.value = 0
        dos_block_flag.expiration = +inf

Barring any issues with concurrency, the above pseudo-code should mimic the behavior of the anti-DOS rules but in a more readable and comprehensible manner.  In the next article, I'll dive a bit deeper by patching a race condition bug in the rules.


Tuesday, May 17, 2016

ModSecurity for Amazon Linux AMI with Apache 2.4 and ELB

UPDATE:  Check out my online interactive tool for auditing ModSecurity log quickly.

I have been searching for a free open source solution to protect my web application against prying hackers, malicious screen scrapers, illegitimate crawlers, rampant bots and abusive API users.  Besides being free and open source, the minimum requirement is that the solution can identify rogue user IP addresses and blacklist them if necessary.  Preferably, the solution can also protect (somewhat) against denial-of-service (DOS) attack and implement API rate limiting.

My system requirements are:
  • Amazon ELB
  • EC2 Nodes
  • Amazon Linux AMI
  • Apache 2.4 (MPM Event)

Blacklist IP Addresses


Since my EC2 nodes are behind a load balancer, simple traditional solution like iptables which operates at the TCP layer will not work because it will pick up the IP address of the load balancer instead of the real user IP address which is being stored at the application layer in X-Forwarded-For of the HTTP header by the load balancer.

To identify and log rogue user IP addresses, you can modify Apache configuration file at /etc/conf/httpd.conf.  Edit the LogFormat lines to include "%{X-Forwarded-For}i".  For example, the edited lines may look like:

LogFormat "%{X-Forwarded-For}i %h %l %u %t \"%r\" %>s %b \"%{Referer}i\" \"%{User-Agent}i\"" combined
LogFormat "%{X-Forwarded-For}i %h %l %u %t \"%r\" %>s %b" common

Then, restart Apache with sudo service httpd restart.

From now on, the user IP will be logged in the first field of each line of the access log at /var/log/httpd/access_log:

X.X.X.X, Z.Z.Z.Z 127.0.0.1 - - [16/May/2016:16:39:03 +0000] "POST / HTTP/1.1" 200 930 "-" "-"

With the user IP address available in the log, you can blacklist a user in different ways.  Without installation of additional modules or tools, you can blacklist manually by adding the IP address directly to the .htaccess file.  The following lines blacklist two IP addresses - X.X.X.X and Y.Y.Y.Y:

SetEnvIF X-Forwarded-For "(,| |^)X\.X\.X\.X(,| |$)" IP_BLACKLIST
SetEnvIF X-Forwarded-For "(,| |^)Y\.Y\.Y\.Y(,| |$)" IP_BLACKLIST
deny from env=IP_BLACKLIST

To automate blacklisting, you can install tools like Fail2Ban with sudo yum install fail2ban.  Fail2Ban will monitor the Apache log, extract the user IP and ban based on defined rules.  For more information, check out the numerous online materials available.


ModSecurity


There are a few free solutions available for DOS protection.  For example, there is the Apache module mod_evasive.  To the best of my knowledge, mod_evasive by itself does not work for a web server located behind a load balancer or proxy because it cannot access the user IP from the X-Forwarded-For header field.  The additional installation of mod_rpaf is required to bypass the limitation.  At the time of writing, the only way to install both modules on Amazon Linux for Apache 2.4 is to download and compile the source code.  Furthermore, mod_evasive is only compatible with Apache running in prefork mode so if your Apache is using MPM worker or event, you are out of luck.  To find out which mpm module Apache is using, check the configuration file at /etc/httpd/conf.modules.d/00-mpm.conf

The alternative solution I have been exploring is ModSecurity.  To install, run sudo yum install mod24_security.  ModSecurity is a web application firewall (WAF) designed to protect Apache, NGINX and IIS against common hacking exploits.  It works by examining web requests against a set of rules to identify malicious traffic pattern (e.g. HTTP header missing user-agent) and execute the corresponding actions (e.g. drop connection).  To make life easier, you can download a predefined set of generic attack detection rules called the OWASP ModSecurity Core Rule Set (CRS) via sudo yum install mod_security_crs.  You can take a look at what the rules look like at https://github.com/SpiderLabs/owasp-modsecurity-crs

The CRS rules are installed at /etc/httpd/modsecurity.d/activated_rules.  You may also add your own rules at /etc/httpd/modsecurity.d/local_rules.  Out of the box, the CRS rules will likely generate many false alarms for your particular website.  This means it will inadvertently shut your users off from your site if you are not careful.  For example, it may mistakenly identify a legitimate HTTP POST request with more than 255 parameters as an exploit even if your application expects it.

At the minimum, before you deploy ModSecurity to production use, find the following line from ModSecurity configuration file at /etc/httpd/conf.d/mod_security.conf

SecRuleEngine On

and change it to:

SecRuleEngine DetectionOnly

This sets ModSecurity to detection mode so it only reports potential exploits without enforcement.  Every time you make changes to the configuration or rules, you must restart Apache with sudo service httpd restart.  If everything goes well, your web application should function normally as before while ModSecurity checks every web requests and log potential problems to /var/log/httpd/modsec_audit.log.

You can control what information ModSecurity should log by editing the configuration file at /etc/httpd/conf.d/mod_security.conf

SecAuditLogParts ABHZ

For example, you can set it to log the request headers, request body, response headers, etc.  A log entry for a potentially malicious web request may look like this:


--61080530-B--
POST /index HTTP/1.1
host: my_website123.com
Accept: application/json, text/javascript, */*; q=0.01
Accept-Encoding: gzip, deflate
Accept-Language: en-US,en;q=0.8
Content-Type: application/x-www-form-urlencoded; charset=UTF-8
Referer: https://my_website123/index
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/50.0.2661.102 Safari/537.36
X-Requested-With: XMLHttpRequest
X-Forwarded-For: X.X.X.X
X-Forwarded-Port: 443
X-Forwarded-Proto: https
Content-Length: 12056
Connection: keep-alive

--61080530-H--
Message: Warning. Operator GT matched 255 at ARGS. [file "/etc/httpd/modsecurity.d/activated_rules/modsecurity_crs_23_request_limits.conf"] [line "31"] [id "960335"] [rev "2"] [msg "Too many arguments in request"] [severity "WARNING"] [ver "OWASP_CRS/2.2.8"] [maturity "9"] [accuracy "9"] [tag "OWASP_CRS/POLICY/SIZE_LIMIT"]
Apache-Handler: application/x-httpd-php
Stopwatch: 1463421036197726 318695 (- - -)
Stopwatch2: 1463421036197726 318695; combined=64071, p1=199, p2=63680, p3=0, p4=0, p5=120, sr=67, sw=72, l=0, gc=0
Producer: ModSecurity for Apache/2.8.0 (http://www.modsecurity.org/); OWASP_CRS/2.2.8.
Server: Apache
Engine-Mode: "DETECTION_ONLY"


In this example, WebSecurity reports that a web request to https://my_website123/index originating from X.X.X.X violates one of the CRS rule for having more than 255 HTTP POST parameters.  The rule ID is 960335.

You can disable a particular rule by adding the following line to /etc/httpd/modsecurity.d/local_rules/modsecurity_localrules.conf

SecRuleRemoveById 960335

Removing a rule may weaken the firewall you are trying to build.  Instead, you can modify the rule to match your traffic pattern.  For the HTTP POST parameter limit violation, you can also increase the tx.max_num_args parameter value in /etc/httpd/modsecurity.d/modsecurity_crs_10_config.conf.


Denial of Service (DOS) Protection


Getting back to my original purpose of setting up a firewall, I can now use ModSecurity to blacklist IPs as well as protect (somewhat) against denial of service attack by using the anti-automation rule set modsecurity_crs_11_dos_protection.conf:

#
# Anti-Automation rule set for detecting Denial of Service Attacks. 
#
#
# Enforce an existing IP address block and log only 1-time/minute
# We don't want to get flooded by alerts during an attack or scan so
# we are only triggering an alert once/minute.  You can adjust how often
# you want to receive status alerts by changing the expirevar setting below.
#
SecRule IP:DOS_BLOCK "@eq 1" "chain,phase:1,id:'981044',drop,msg:'Denial of Service (DoS) Attack Identified from %{tx.real_ip} (%{tx.dos_block_counter} hits since last alert)',setvar:ip.dos_block_counter=+1"
SecRule &IP:DOS_BLOCK_FLAG "@eq 0" "setvar:ip.dos_block_flag=1,expirevar:ip.dos_block_flag=60,setvar:tx.dos_block_counter=%{ip.dos_block_counter},setvar:ip.dos_block_counter=0"

#
# Block and track # of requests but don't log
SecRule IP:DOS_BLOCK "@eq 1" "phase:1,id:'981045',t:none,drop,nolog,setvar:ip.dos_block_counter=+1"

#
# skipAfter Check
# There are different scenarios where we don't want to do checks -
# 1. If the current IP address has already been blocked due to high requests
# In this case, we skip doing the request counts.
#
SecRule IP:DOS_BLOCK "@eq 1" "phase:5,id:'981046',t:none,nolog,pass,skipAfter:END_DOS_PROTECTION_CHECKS"

#
# DOS Counter
# Count the number of requests to non-static resoures
# 
SecRule REQUEST_BASENAME "!\.(jpe?g|png|gif|js|css|ico)$" "phase:5,id:'981047',t:none,nolog,pass,setvar:ip.dos_counter=+1"

#
# Check DOS Counter
# If the request count is greater than or equal to user settings,
# we then set the burst counter
# 
SecRule IP:DOS_COUNTER "@gt %{tx.dos_counter_threshold}" "phase:5,id:'981048',t:none,nolog,pass,t:none,setvar:ip.dos_burst_counter=+1,expirevar:ip.dos_burst_counter=%{tx.dos_burst_time_slice},setvar:!ip.dos_counter"

#
# Check DOS Burst Counter and set Block
# Check the burst counter - if greater than or equal to 2, then we set the IP
# block variable for 5 mins and issue an alert.
#
SecRule IP:DOS_BURST_COUNTER "@ge 2" "phase:5,id:'981049',t:none,log,pass,msg:'Potential Denial of Service (DoS) Attack from %{tx.real_ip} - # of Request Bursts: %{ip.dos_burst_counter}',setvar:ip.dos_block=1,expirevar:ip.dos_block=%{tx.dos_block_timeout}"

SecMarker END_DOS_PROTECTION_CHECKS


You can tailor the burst detection pattern by editing the file at /etc/httpd/modsecurity.d/modsecurity_localrules.conf:

#
# -- [[ DoS Protection ]] ----------------------------------------------------------------
#
# If you are using the DoS Protection rule set, then uncomment the following
# lines and set the following variables:
# - Burst Time Slice Interval: time interval window to monitor for bursts
# - Request Threshold: request # threshold to trigger a burst
# - Block Period: temporary block timeout
#
SecAction \
  "id:'900015', \
  phase:1, \
  t:none, \
  setvar:'tx.dos_burst_time_slice=60', \
  setvar:'tx.dos_counter_threshold=100', \
  setvar:'tx.dos_block_timeout=600', \
  nolog, \
  pass"


ModSecurity is a powerful tool to protect web applications and as such it comes with a learning curve.   I have only touched on the basics in this blog entry.  Hopefully, I can devote some more blog time to it as I pick up the tool myself.

To develop your own tunnel vision quickly as I have been doing, I recommend taking a look at the official documentation at:

https://github.com/SpiderLabs/ModSecurity/wiki/Reference-Manual


Tuesday, April 19, 2016

Monitoring YouTube Channel Comments with PHP



If you are a programmer who owns or follows YouTube channels and wishes to monitor and keeps track of the latest posted comments programmatically using PHP and MySQL, you can use the YouTube Data API along with an API key provided by Google.  The Google API key is available at the Google developers console and you must enable YouTube Data API there in order to access the interface.

The YouTube RESTful Data API is fairly well documented and contains code samples for at least Java, PHP and Python.  To expedite development, it also has a "Try It!" snippet where you can test your API call live from the page.  You have two authentication options to access the API - OAuth or API key.  For simplicity, we will be using an API key.

In this little hackathon exercise, I'll provide the complete running PHP and MySQL code to crawl the latest channel and video comments from YouTube.  The crawling repeats in an infinite loop (while observing API rate limiting) so the comments are constantly refreshed to the database.  A web page for viewing comments is added with capabilities such as pagination, sorting and searching all thanks to the wonderful javascript Datatables.  The end result looks like this:

Screenshot of crawled comments on web page.


How to Set it Up?  (Go to Bitbucket)


To get it up and running, make sure you have MySQL and PHP set up first.  After that, do the following steps:

1. Download the PHP source code from Bitbucket.  At the time of writing, the repo contains:

crawler.php  Monitors and crawls YouTube channel and video comments
top.secrets.php  Database access info and Google API key
index.php  Simple web UI using Datatables
server_processing.php  DataTables example server-side processing script
ssp.class.php  Helper functions for building DataTables server-side processing SQL query

2. Add database table for storing YouTube comments.

   CREATE TABLE comments (  
     `id` INT(10) UNSIGNED NOT NULL AUTO_INCREMENT,  
     `crawl_timestamp` INT UNSIGNED NOT NULL,  
     `timestamp` INT UNSIGNED NOT NULL,  
     `uid` VARCHAR(100) NOT NULL,  
     `pid` VARCHAR(100),  
     `username` VARCHAR(255) NOT NULL,  
     `message` TEXT NOT NULL,  
     PRIMARY KEY (`id`)  
   ) ENGINE=InnoDB DEFAULT CHARSET=UTF8;  

A simple explanation of the table structure is warranted.

crawl_timestamp  Unix timestamp when comment was crawled from YouTube
timestamp  Unix timestamp when comment was published
uid  Comment ID assigned by YouTube
gid  Parent comment ID. For top level comments, gid is same as uid
username  Commentator username
message  Comment text

Add unique index on uid column to support "replace into" query.

 CREATE UNIQUE INDEX index_comments_uid ON comments (uid);  

3. Configure top.secrets.php with your database access information and Google API key.

4. Execute "php crawler.php" at command console to begin crawling.  The crawled comments are updated to database.


How Does it Work?


The actual PHP code for crawling is fairly simple and short (see code snippet below).  The crawler runs in an infinite loop.  Each loop iteration crawls all thread comments and replies for the specified YouTube channel and updates them to the database.  Upon completion of an iteration, previously crawled comments marked with an earlier crawl timestamp are deleted from database so that the database always stores the latest comments.  In the script, I hardcoded the minimum number of most recent comments to be retrieved to 100.  While it's possible that the crawler may retrieve more than the given minimum, it will not retrieve less than the minimum unless the total number of comments in the channel is less than 100.

 require('top.secrets.php');  
 date_default_timezone_set('UTC');  
 $maxCount = 100; // min number of latest comments to monitor  
 $secondsInYear = 365 * 24 * 60 * 60;  
 while (true) {  
   $crawledThreads = 0;  
   $crawledReplies = 0;  
   $crawlTimestamp = time(); // comments crawled in this loop iteration are timestamped  
   $nextCommentPageToken = null;  
   do {  
     $nextCommentPageToken = fetchThread($key, $channelId, $nextCommentPageToken, $threadJson);  
     sleep(1); // respect api rate limiting  
     // parse each thread and replies  
     if (array_key_exists('items', $threadJson)) {  
       foreach ($threadJson['items'] as $thread) {  
         // parse thread  
         $threadId = $thread['id'];  
         $threadData = parseComment($threadId, $threadId, $thread['snippet']['topLevelComment']);  
         $threadTimestamp = $threadData['timestamp'];  
         // save thread to db  
         persistDatabase($servername, $username, $password, $dbname, $crawlTimestamp, $threadData);  
         $crawledThreads++;  
         // parse replies  
         $totalReplyCount = $thread['snippet']['totalReplyCount'];  
         if ($totalReplyCount) {  
           $replies = $thread['replies']['comments'];  
           if (count($replies) == $totalReplyCount) {  
             // fetch comment replies from thread json  
             foreach ($replies as $reply) {  
               // save reply to db  
               persistDatabase($servername, $username, $password, $dbname, $crawlTimestamp, parseComment($reply['id'], $threadId, $reply));  
               $crawledReplies++;  
             }  
           }  
           else {  
             // fetch comment replies via api call  
             $nextRepliesPageToken = null;  
             do {  
               $nextRepliesPageToken = fetchReplies($key, $threadId, $nextRepliesPageToken, $repliesJson);  
               sleep(1); // respect api rate limiting  
               if (array_key_exists('items', $repliesJson)) {  
                 foreach ($repliesJson['items'] as $reply) {  
                   // save reply to db  
                   persistDatabase($servername, $username, $password, $dbname, $crawlTimestamp, parseComment($reply['id'], $threadId, $reply));  
                   $crawledReplies++;  
                 }  
               }  
             } while ($nextRepliesPageToken);  
           }  
         }  
         // threads older than 1 year have no comments so stop crawling if min comments quota is met  
         if (time() - $threadTimestamp > $secondsInYear && $crawledThreads + $crawledReplies >= $maxCount) {  
           break 2;  
         }  
       }  
     }  
   } while ($nextCommentPageToken);  
   // delete previously crawled comments from db  
   refreshDatabase($servername, $username, $password, $dbname, $crawlTimestamp);  


What's Next?


To keep the code to barebone minimum, I have omitted error handling, logging, batch SQLs and other things to make the code robust and optimized.  Feel free to do anything you'd would like with the code but I'd love to hear what you are doing with it!

Sunday, March 20, 2016

Better Time Management for Programmers

Here's a common scheduling problem we, the programmers, will likely face in our career at one point or another.

You have a project or program that will take a long time to finish and you only have a fixed maximum time slot to work on it every day.  The project is structured and divided into a series of smaller tasks or milestones such that:
  1. The tasks are ordered and performed sequentially.  This means a following task cannot start until the previous task is finished.

  2. The duration of each task differs.  Some tasks take longer than others but each task lasts shorter than the daily time slot allowed.  Some tasks may be so short that it's possible to finish several within the same time slot.

  3. Tasks have overhead time penalty.  The first and last task completed in a time slot incur set-up and tear-down time penalty, respectively.  The penalty amount depends on the task.
To illustrate the problem with an example, let's say your project has 5 sequential tasks or milestones - A, B, C, D and E.  You can only work on the project at most 2 hours (120 minutes) a day.  The time it takes to finish each task along with set-up and tear-down penalty time are:

Task Execution Time Set-up Time Tear-down Time
A 50 10 5
B 30 5 0
C 40 15 5
D 20 0 10
E 30 5 5

All time units are in minutes.  Set-up and tear-down time are the time penalty for context switching tasks in and out of the time slot.  In real-life, these could be ceremonious activities such as booting up the machines, push or pulling source code from version control, reading or documenting code, loading or persisting large data set to or from memory, powwows, soaking up chakra, etc.

There are many ways of scheduling the tasks.  Some are valid and some are not.  For example, if you choose task A, B and C on the first day, the set-up time is 10 (A's set-up time).  Tear-down time is 5 (C's tear-down time).  Task A, B and C take 50, 30 and 40 minutes to execute, respectively.  The total time to complete A, B and C is 10 + 50 + 30 + 40 + 5 = 135 minutes.  Since your maximum daily time slot is 120 minutes, this combination exceeds the time slot so it's not a valid choice.

As an example of a valid scheduling, you can assign A and B to the first day, C and D to the second, and E to the third.  The total time to complete the project is:

(A + B) + (C + D) + E = (10 + 50 + 30 + 0) + (15 + 40 + 20 + 10) + (5 + 30 + 5) = 215 minutes

As much as we programmers like to program, we like downtime, too.  The quicker we finish the project the better.  So how do we find the best scheduling assignment?  There is a simple and clever solution to this thanks to Prin et al [1] from the seemingly unrelated problem domain of vehicle routing.  I'll explain the intuition behind the idea.  For those who are looking for an efficient labeling algorithm implementing the idea, please refer to Prin et al [1].

First, we'll represent the scheduling problem with a graph:

Graphical representation of tasks

In the above graph, there are two types of vertices - task vertex and breakpoint vertex.  Breakpoint vertex X represents the starting and ending point of a time slot.  Task vertex A, B, C, D and E represent the 5 tasks in our example problem.  A directed edge between X and task vertex represents the set-up time of the task while a directed edge between task vertex and X represents the tear-down time of the task.  The edges between tasks represent the time required to transition from one task to another which is 0 in our case.  Lastly, each vertex is weighted with the execution time of the task.  The execution time of vertex X is 0.

In reading of this graph, the schedule of assigning A and B to the first day, C and D to the second, and E to the third, is represented by path XABXCDXEX.  The total project completion time is the sum of edge and vertex weights of the path.

Next, we'll construct a simple auxiliary graph as such:


The auxiliary graph above has 6 vertices matching our first graph.  Each edge represents a single time slot schedule as described in the table below.  In the auxiliary graph, we have omitted edges whose time slot schedule exceeds the maximum 120 minutes allowed.

EdgeTime Slot ScheduleSet-up + Execution + Tear-down Time
(X, A)XAX65
(X, B)XABX90
(X, C)XABCX135
(X, D)XABCDX160
(X, E)XABCDEX185
(A, B)XBX35
(A, C)XBCX80
(A, D)XBCDX105
(A, E)XBCDEX130
(B, C)XCX60
(B, D)XCDX85
(B, E)XCDEX110
(C, D)XDX30
(C, E)XDEX55
(D, E)XEX40

Any path that starts from vertex X and ends at vertex E on the auxiliary graph represents a project schedule.  For example, path XACE consists of 3 edges - (X, A), (A, C) and (C, E).  Each edge can be decoded into a time slot schedule using the above table.  For example, edge (X, A) represents time slot schedule of XAX, edge (A, C) represents (XBCX) and edge (C, E) represents (XDEX).  Altogether, path XACE means the project is split into 3 time slots.  Task A is assigned to the first time slot, task B and C the second, while task D and E the third.

To find the optimal project schedule, you just need to compute the shortest path from X to E on the auxiliary graph using Dijkstra's algorithm or a similar variant.  In the case of our example, the shortest path is XADE which means the project is split into 3 time slots.  Task A is assigned to the first time slot, task B, C and D the second, while task E the third.  The total project completion time is 210 minutes.

References


[1] Christian Prins, A simple and effective evolutionary algorithm for the vehicle routing problem, Computer and Operations Research, 31 (2004), 1985-2002.