*.blog

by Justin Collins

Simple Readers-Writer Lock Gem

A readers-writer lock can be used to allow many concurrent read-only operations on a resource but ensure exclusive access for modifying operations performed by “writers”. For my purposes, I needed a readers-writer lock at the thread level, basically to control access to a shared array. In my scenario, the array is accessed through a server which may server many clients at once. Some requests will be to read elements from the array, while other requests might be adding elements to the array. There is no reason to restrict reads to one client at a time, but elements need to be added while no other client is reading or writing to the array.

My implementation is very simple (the entire RWLock class is 25 lines of code) because it relies on Ruby’s SizedQueue class. SizedQueue provides a thread-safe queue with a maximum size. If a thread attempts to add elements to a queue that is full, it will be blocked until an element is removed from the queue to make room. This is a key piece of funtionality used for the readers-writer lock implementation.

The RWLock class only really needs to provide two methods: one to provide read access, and one to provide write access. Since this is Ruby, the methods will take a block to execute the reading/writing code:

1
2
3
4
5
6
7
8
9
10
11
12
13
class RWLock
  def read_sync
    #lock magic
    yield
    #lock magic
  end

  def write_sync
    #lock magic
    yield
    #lock magic
  end
end

The internal state of the lock will be a SizedQueue and a Mutex.

1
2
3
4
  def initialize max_size = 10
    @write_lock = Mutex.new
    @q = SizedQueue.new(max_size)
  end

The SizedQueue will essentially be used as a counting semaphore. Each time a reader enters read_sync, the lock will push an element onto the queue. What the element actually is doesn’t matter, but I used true because it’s cheap. If the queue is full, the reader will block until a space has opened up.

1
2
3
4
5
6
  def read_sync
    @q.push true
    yield
  ensure
    @q.pop
  end

When a writer calls write_sync, it synchronizes on the mutex to prevent multiple concurrent writers. Then it adds n elements to the queue, where n is equal to the maximum size of the queue.

This has two effects: first, the writer is forced to wait for all current readers to finish. Second, it essentially prevents any new readers from gaining access (there is a small chance one will sneak in, but the writer will still have to wait for it).

1
2
3
4
5
6
7
8
9
10
11
  def write_sync
    @write_lock.synchronize do
      @q.max.times { @q.push true }

      begin
        yield
      ensure
        @q.clear
      end
    end
  end

Once the writer is finished, the queue is cleared, allowing all waiting readers to jump in. It is most likely waiting readers will get in before waiting writers, since the write mutex is held while the queue is emptied, but no effort is made to guarantee that one way or another. In practice, though, this seems to balance well between readers and writers.

One obvious downside of this overall approach is the SizedQueue limits the number of concurrent readers. A larger queue will cause writers to wait longer (assuming many readers) while a smaller queue may cause readers to wait on other readers. The upside is readers cannot monopolize the resource and cause writer starvation.

Unfortunately, SizedQueue#clear has been broken forever, since it was simply inherited from Queue and didn’t actually notify waiting threads that the queue is empty. For some reason, this does not appear to matter in Ruby 1.8, but in Ruby 1.9 and 2.0 it caused a deadlock.

This has been fixed in Ruby 1.9.3p545 and 2.1.1. For broken versions, the RWLock gem monkey-patches SizedQueue to fix the behavior. Unfortunately, Ruby 2.0 also had a bug in SizedQueue#push, so it is completely incompatible. The code does work under JRuby, but there are faster implementations using Java primitives.

RWLock is available as a gem and of course the code is on GitHub.

Testing Brakeman Against 253 Rails Apps

Here is some information about how Brakeman is tested!

Basic Testing and Continuous Integration

Brakeman does have a few unit tests…pitifully few. In fact, Brakeman had no tests at all until version 0.5.2, nearly a year after Brakeman’s initial public release. Unit testing Brakeman remains difficult, since much of the code relies on data built up from scanning an entire Rails application.

As such, the majority of tests in Brakeman rely on scanning sample applications and checking the resulting reports for an expected set of warnings. There are tests for the presence and absence of specific warnings, as well as checking for the specific number of warnings and an absence of reported errors. Since writing tests is pretty tedious, there is a script which generates the Ruby code to asserts the presence of reported warnings. This script takes the same arguments as Brakeman, so it’s simple to generate a set of tests for a specific scenario.

1
2
3
4
5
6
7
8
9
def test_information_disclosure_local_request_config
  assert_warning :type => :warning,
    :warning_code => 61,
    :fingerprint => "081f5d87a244b41d3cf1d5994cb792d2cec639cd70e4e306ffe1eb8abf0f32f7",
    :warning_type => "Information Disclosure",
    :message => /^Detailed\ exceptions\ are\ enabled\ in\ produ/,
    :confidence => 0,
    :relative_path => "config/environments/production.rb"
end

The tests run on Travis CI which is integrated with GitHub. This is especially helpful for testing compatibility with Ruby 1.8.7, which many Rails applications still run on and Brakeman will probably continue supporting for a long time.

Regression Testing with a Wide Net

Unfortunately, the sample applications Brakeman uses for tests are quite limited, not real, and generally just test very specific warnings or previous bugs. To gain higher confidence that Brakeman is not too broken, Brakeman is run against a set of 253 open source Rails applications I have managed to scrape together. (If you have an open source application to add to this test set, please let me know!)

The scans are run on my personal machine - six jobs in parallel, which takes about nine minutes total. After puttering around with a few different approaches, I ended up simply using the Queue class from Ruby’s standard library as the job queue. In a Frankenstein combination, a shell script starts up a JRuby process, which builds the Brakeman gem and then runs six threads for scan jobs. Each job launches Brakeman as an external process running under MRI 1.9.3 and, if successful, produces a JSON report. The JSON report is then augmented with some information about the Brakeman commit and the app that was scanned.

When all the apps have been scanned, the JSON reports are tarred up and sent to a server. I use DigitalOcean (referral link!) because I needed an Ubuntu setup and their API lets me use some handy scripts to spin the server up and down whenever I need it (and only pay for when it’s up).

On the server, the reports are unpacked and imported into a RethinkDB database. Since RethinkDB stores JSON documents, it’s simple to dump the JSON reports from Brakeman in there. I just have two tables: one just contains commit SHAs and their timestamps, and the other contains the actual reports. I have secondary indexes on the reports to efficiently look them up by the name of the Rails app or the Brakeman SHA.

A small Sinatra app serves up some basic graphs and allows two commits to be compared:

Brakeman Graphs

This “system” is not open source at the moment, but probably will be in the future when I’ve removed hard-coded stuff.

Anyhow, since I have all these reports, I can share some data…but just be forewarned you can’t really draw any conclusions from it!

Numbers!

This is the RethinkDB query for warnings per category, in JavaScript since I ran it in the web UI:

1
2
3
4
5
6
r.db("brakeman").
  table("reports").
  getAll("25a41dfcd9171695e731533c50de573c71c63deb", {index: "brakeman_sha"}).
  concatMap(function(rep) { return rep("brakeman_report")("warnings") }).
  groupBy("warning_type", r.count).
  orderBy(r.desc("reduction"))
Warning Category Count
Cross Site Scripting 6669
Mass Assignment 3385
SQL Injection 1353
Remote Code Execution 458
Denial of Service 440
Redirect 232
Format Validation 230
Attribute Restriction 205
File Access 200
Session Setting 169
Dynamic Render Path 140
Command Injection 116
Cross-Site Request Forgery 96
Default Routes 67
Response Splitting 44
Dangerous Eval 43
Dangerous Send 33
Nested Attributes 5
Information Disclosure 2
Authentication 2

Some educated guesses about these numbers:

  • Mass assignment numbers are likely high because they include warnings about dangerous attributes that are whitelisted.
  • Remote code injection is mostly uses of constantize and similar methods.
  • Most denial of service warnings are calls to to_sym on parameters
  • Response splitting is interesting because it is only reported in regards to CVE-2011-3186 which was fixed in Rails 2.3.13.

This last point made me curious about the Rails versions in use by the applications. Keeping in mind these apps are not necessarily up-to-date, they represent at least 37 different versions! Some were reported as unknown versions.

Here are the top ten:

Rails Version Count
3.2.13 26
2.3.5 19
3.0.3 18
3.2.14 14
4.0.0 11
3.2.12 9
2.3.8 8
3.2.11 8
3.0.0 7
3.1.0 6

With so many applications and nearly 14,000 warnings, there is a lot more information to go through here.

For now this process is used to help test new Brakeman code and avoid regressions. It’s stopped quite a few bugs from going out!

Fast Compact Sparse Bit Sets

Imagine you need a relatively compact data structure for quickly checking membership of mostly-consecutive non-negative integers. (If this sounds really specific, it is because it is precisely what I needed for a particular project.)

The Ruby standard library contains a Set class which may be a good starting point. Set is actually implemented as a Hash with the Set elements as keys and true as the values. Thus the overhead for storing a value in the Set is essentially only the value itself since all keys point to the same true object. Assuming a 64-bit machine, the overhead will be 64 bits per value. This seems reasonable, but given the specific limitations of the values we wish to store, perhaps we can do better?

Bit Sets

A bit set is a compact data structure of binary values where membership is indicated by setting a bit to 1. The position of the bit indicates the element value. For example, the second bit from the right might be used to indicate whether or not the value 1 is in the set.

One method to determine membership is to AND the bit set with a mask with only the desired bit set to 1. If the result is 0, the value is not in the set. If it is any other result (actually the mask itself, but the zero check is sufficinet), the value is a member of the set.

In Ruby, this looks like

1
bitset & (1 << num) != 0

For example, to check if the value 4 is in the set, we use the mask 00010000 (the 5th bit from the right is set to 1) which is the decimal value 8:

Bit Set Checking Example 1

Since the result is zero, we know the value 4 is not in the set.

If we check for the value 6, the result is not zero, indicating the value is a member of the set:

Bit Set Checking Example 2

Now, instead of 64 bits per value, it only requires a single bit! Now we just need to put a lot of bits together, either by using a long string or a bunch of integers in an array.

Sparse Bit Sets

The problem with a long binary string or an array of integers is that membership is entirely position-based. To store the value 1000, the data structure requires 1001 bits, all but one of which is set to 0. This is quite inefficient, especially for very large values.

One solution is to create a sparse bit set by combining a hash table with bit sets as values. The hash table keys provide fast look up of the correct bit set, then the bit set is checked for the desired element. The keys indicate the lowest value stored in the bit set (e.g., the decimal key 4 pointing to the binary bit set 00000001 would mean the value 4 is in the set).

Below is an example of a hash table using integer keys and 8 bit integers for the bit sets:

Sparse Bit Set Example

The average overhead is ⌊(m * n) / w⌋ + m bits, where m is the number of values (assumed to be consecutive), w is the number of bits per bit set, and n is the number of bits per key. In 64-bit Ruby, if we use integers for the bit sets, n = 64 and w = 62*. This works out to an average of 2 bits per value in the set. Of course, a single value incurs the overhead of both the key and the bit set: 128 bits! But if there are many consecutive values, the cost per value begins to shrink. For example, the numbers 0 to 61 can be stored in a single bit set, so 62 values can be stored in the 128 bits and we are back to about 2 bits per value.

Note that while it is best to use consecutive values which fit neatly into the bit sets (in this case, runs of 62 integers), the sequences can start and end at arbitrary points with only a little “wasted” overhead. To store just the number 1000, we now only need 128 bits, not 1001.

On top of the space savings, the membership checks remain fast. Still assuming 64-bit Ruby, to determine if a value is in the table look up index i = value / 61. Then check the bit set with bitset & (1 << (value % 61) != 0 as previously. (The divisor is 61 because there are 62 bits, but the values are 0 to 61).

Space Efficiency

I have implemented a Ruby version of the data structure described above which I call the Dumb Numb Set (DNS).

To measure the space used by the bit sets, we compare the Marshal data size for the bit sets versus regular Hashes (using true for all values, just like a Ruby Set).

These are the results for perfectly ordered data on a 64-bit version of Ruby 1.9.3 (size is number of bytes):

1
2
3
4
5
6
7
8
9
10
11
12
Items        Hash         DNS      %reduction
---------------------------------------------
   1   |           7  |        41   |-486%
 100   |         307  |        61   |  80%
  1k   |        4632  |       253   |  95%
 10k   |       49632  |      2211   |  96%
100k   |      534098  |     24254   |  95%
  1M   |     5934098  |    245565   |  96%
 10M   |    59934098  |   2557080   |  96%
100M   |   683156884  |  26163639   |  96%
  1B   |         ?    | 262229211   |   ?
---------------------------------------------

At 1 billion items, my machine ran out of memory.

For a single item, as expected, overhead in the DNS is quite high. But for as little as 100 items in the set, the DNS is considerably more compact.

This is, however, the best case scenario for the DNS. Less perfectly dense values cause it to be less efficient. For very sparse values, a Hash/Set is probably a better choice.

Even Better Space Efficiency

It may not surprise you to find out I was very interested in minimizing the serialized version of the sparse bit set for sending it over a network. In investigating easy but compact ways of doing so, I realized the Marshal data for Hashes and integers is not very compact, especially for large integers.

Fortunately, there is an existing solution for this scenario called MessagePack. For storing 1 million values, serialized size is reduced from 245,565 to 196,378 bytes (20%). The DNS will use MessagePack automatically if it is installed.

Performance

Somewhat surprisingly, the DNS is quite fast even when compared to MRI Ruby’s Hash implementation.

With MRI Ruby 1.9.3p448 (x86_64) and 1 million values:

1
2
3
4
5
6
7
8
9
10
11
                           user     system      total        real
Hash add random            0.540000   0.020000   0.560000 (  0.549499)
DumbNumbSet add random     0.850000   0.020000   0.870000 (  0.864700)
Hash add in order          0.540000   0.020000   0.560000 (  0.556441)
DumbNumbSet add in order   0.490000   0.000000   0.490000 (  0.483713)
Hash add shuffled          0.570000   0.020000   0.590000 (  0.589316)
DumbNumbSet add shuffled   0.540000   0.010000   0.550000 (  0.538420)
Hash look up               0.930000   0.010000   0.940000 (  0.940849)
DNS look up                0.820000   0.000000   0.820000 (  0.818728)
Hash remove                0.980000   0.030000   1.010000 (  0.999362)
DNS remove                 0.950000   0.000000   0.950000 (  0.953170)

The only operation slower than a regular Hash is inserting many random values. All other operations are roughly equal.

Conclusion

For my specific scenario, a simple custom data structure was just as fast as a built-in data structure, but required significantly less space for the expected use case.

There are other solutions for this type of problem, but it should be noted I only really care about fast insertion, fast membership checks, and compact representation. Additionally, values may be very large, although I attempt to keep them within the Fixnum range for Ruby (i.e. less than 262 - 1). This rules out some implementations which require arrays the size of the maximum value!

I also did not want to deal with compression schemes, of which there are quite a few, since my sets were going to be dynamic. I imagine there are very efficient implementations for fixed data sets.

Footnote: Integer Size in Ruby

Integers in 32-bit MRI Ruby only have 30 bits available, and in 64-bit MRI Ruby they only have 62 bits available:

1
2
3
4
5
$ irb
1.9.3p448 :001 > ("1" * 62).to_i(2).class
 => Fixnum
1.9.3p448 :002 > ("1" * 63).to_i(2).class
 => Bignum

Avoiding SQL Injection in Rails

SQL injection (SQLi) is any situation in which a user can manipulate a database query in an unintended manner. Consequences of SQL injection vulnerabilites range from data leaks, to authentication bypass, to root access on a database server. In short, it is a very big deal.

Most Rails applications interact with a database through ActiveRecord, the default and convenient Object Relational Mapping (ORM) layer which comes with Rails. Generally, use of ORMs is safer than not. They can provide abstraction and safety and allow developers to avoid manually building SQL queries. They can embody best practices and prevent careless handling of external input.

Instead of unsafe code like

query = "SELECT * FROM users WHERE name = '#{name}' AND password = '#{password'} LIMIT 1"
results = DB.execute(query)

You can have safer, simpler code like

User.where(:name => name, :password => :password).first

My impression is many people assume the Rails framework will protect them as long as they avoid the “obviously dangerous” methods, like find_by_sql.

Unfortunately, ActiveRecord is unsafe more often than it is safe. It does provide parameterization of queries (the API documentation for which can be found here) for some methods, there are many methods for which it does not. While these methods are not intended to be used with user input, the truth is that has never stopped anyone.

To make it clear how dangerous it can be to use ActiveRecord, consider ActiveRecord::FinderMethods#exists? which queries the database and returns true if a matching record exists. The argument can be a primary key (either integer or string, if a string it will be sanitized), an array consisting of a template string and values to safely interpolate, or a hash of column-value pairs (which will be sanitized).

Here is an example of using exists? to determine if a given user exists:

User.exists? params[:user_id]

This looks harmless, since params[:user_id] is a string, and strings will be sanitized. In fact, the documentation clearly points out not to pass in conditions as strings, because they will be escaped.

However, there is no gaurantee params[:user_id] is a string. An attacker could send a request with ?user_id[]=some_attack_string, which Rails will turn into an array ["some_attack_string"]. Now the argument is an array, the first element of which is not escaped.

To avoid this problem, the user input should be converted to the expected type:

User.exists? params[:user_id].to_i

Or use a hash:

User.exists? :id => params[:user_id]

This should be the approach for all uses of user input. Do not assume anything about values from external sources or what safety mechanisms a method might have.

While working on Brakeman, I thought it would be useful to put together a list of all the unsafe ways one can use ActiveRecord.

To make it easier on myself, I built the list into a Rails application so I could easily test, verify, and record any findings. The source is available here for those who would like try out the examples. The application is a single page of all the queries and example injections. From there one can submit queries and see the results:

Query Example

The resulting information is available at rails-sqli.org, including examples of how SQL injection can occur and the resulting queries. This is basically a big list of what not to do when using ActiveRecord. Again, please feel free to contribute so that the list can be as authoritative as possible and help everyone avoid SQL injection in Rails.

Faster Call Indexing in Brakeman

Background

About a month ago, an issue was reported where Brakeman taking a ridiculously long time on the “call indexing” step. At the time, I was pessimistic about opportunities to improve the performance of call indexing, since it is a pretty simple operation.

Call Indexing

The majority of the checks performed by Brakeman involve finding and examining method calls (e.g., SQL queries). In order to make these checks faster, Brakeman scans an app once and then saves information about each method call in a data structure called the “call index”. This makes searching for specific method calls very fast.

The call index allows search for methods by name and also by the class of the target. For example, it is possible to search for all calls to open on File. It also allows searching via regular expressions for methods and targets.

Investigation

I happened to notice a Rails application in my collection which also seemed to take a long time indexing calls. So I ran it through perftools.rb to see if there was anything interesting going on.

This is the result:

Brakeman 1.8.2 scan

The large amount of time spent in the garbage collector (60%) was high even for Brakeman. But then something else caught my eye:

Call indexing in 1.8.2

This scan spent 4.7% of its time converting Sexps to strings while indexing calls. This seemed excessive.

This is the entirety of the call indexing code:

call_index.rb
1
2
3
4
5
6
7
8
  def index_calls calls
    calls.each do |call|
      @methods << call[:method].to_s
      @targets << call[:target].to_s
      @calls_by_method[call[:method]] << call
      @calls_by_target[call[:target]] << call
    end
  end

@methods and @targets are sets which contain the string versions of all the methods and method targets. This is exclusively used to search for methods and targets via regular expressions.

The call method will always be a symbol…but what about the target? It turns out that while much of the time it is a symbol, if a sane value like :File or :@something cannot be found, then it will be the entire Sexp! This is where Brakeman was wasting time calling Sexp#to_s.

The quick fix was to only store symbol targets in the @targets set, ignoring any other target values.

Results

Scanning the same application with Brakeman 1.8.3 has this result:

Brakeman 1.8.3 scan

Garbage collection time dropped from 60% to 42%. While still very high, this is a good sign. Time spent indexing calls has dropped from 5.4% to 1.8% and the calls to Sexp#to_s have vanished.

The total scan time dropped from 3.5 minutes to about 2 minutes. For the original reporter, scan times went from 78 minutes to 40 seconds.

More Improvements

Looking through Brakeman, it does not currently use the “search via regex” feature for the call index. So the method and target name sets can be removed entirely.

Going even further, nowhere does Brakeman search for targets by any values other than symbols. Note in the graph below that Array#eql? was sampled 1,330 times during call indexing:

Call indexing hashing

Since Sexps are subclassed from Array, it is clear that these calls are generated when using the call[:target] as a hash key (line 6 above). Again, the current Brakeman code only searches for call targets by symbol, never by a full Sexp. There is no reason to the call targets that are Sexps.

This is the modified call indexing code:

Modified call_index.rb
1
2
3
4
5
6
7
8
9
  def index_calls calls
    calls.each do |call|
      @calls_by_method[call[:method]] << call

      unless call[:target].is_a? Sexp
        @calls_by_target[call[:target]] << call
      end
    end
  end

With this code in place, call indexing does not even show up under perftools. Speed improvements vary by project, but this should at least shave off a few seconds. YMMV.

Wrapping Up

Some quick profiling led me to performance improvements where I really did not expect to find them. Sadly, this is one of the cleanest, simplest parts of Brakeman, so I know there are many other instances where Brakeman can be improved. Prior to the introduction of the call index in Brakeman 1.0, I was trying to keep Brakeman scans under 20 minutes (on large applications). Now I worry when scans take longer than a few minutes.

97% of the open source Rails applications I use as test cases can be scanned in less than 30 seconds. Unfortunately, this probably does not reflect scan times for large, commercial applications. Please report any long-running scans! It may lead to more speed improvements like the ones above.