ACIDRain Concurrency Attacks on Database-backed Applications

ACIDRain attacks are a new kind of cyberattack on database-backed applications, in which a cybercriminal systematically exploits concurrency-related vulnerabilities that lead to the violation of an application integrity constraint. This might be for instance, vouchers that should only be spent once, or the checkout price needing to include every item in a shopping cart. An attacker would deliberately drive concurrent requests aimed at triggering and exploiting the weakness through programmatically accessible APIs.

Database transactions are meant to protect application data from integrity violations and corruption despite concurrent access to shared state. In theory, programmers are meant to correctly group their application operations into transactions, thereby preserving application integrity. In reality, database transactions often take place under weak isolation, which can expose programs to a host of concurrency anomalies. In addition, human error during programming may lead to failure in correctly employing transactions in the first place. Furthermore, low transaction volumes disguise many possible concurrency-related errors under normal operations, allowing determined hackers to programmatically exploit them for what Stanford researchers Todd Warszawski and Peter Bailis describe as “fun and profit”.

In their co-authored paper, ‘ACIDRain: Concurrency-Related Attacks on Database-Backed Web Applications’, Warszawski and Bailis outline the threat posed by ACIDRain attacks in the wild through studying 12 of the most popular self-hosted eCommerce applications. In doing so, they identify 22 critical ACIDRain attacks, which have allowed attackers to corrupt store inventory, over-spend gift cards, and steal inventory. As Warszawski and Bailis stress, “These attacks are not theoretical: ACIDRain attacks have already occurred in a handful of applications in the wild, including one attack which bankrupted a popular Bitcoin exchange”.

There are two types of anomaly that ACIDRain attacks could trigger, dependent on the application involved:

  1. Level-based isolation anomalies, which are races due to isolation settings at the database-level i.e. the database may not support serializability, or may not have been configured to do so (this is the case for most deployed databases in the wild).
  2. Scoping isolation anomalies, which occur when an application programmer fails to correctly encapsulate logic using transactions. This enables concurrent requests to impact behavior that could not have arisen sequentially.

The researchers make clear that they “assume that an attacker can only access the web application via concurrent requests against publicly-accessible APIs (e.g., HTTP, REST). That is, to perform an ACIDRain attack, the attacker does not require access to the application server, database server, execution environment, or logs. Our proposed analysis techniques use full knowledge of the database schema and SQL logs, but, once identified, an attacker can exploit the vulnerabilities we consider here using only programmatic APIs.2 This threat model applies to most Internet sites today”.

How are Anomalies Detected?

In their paper, Warszawski and Bailis describe the initial detection of these anomalies as “challenging” because many potential anomalies are never triggered as a result of limited concurrency, which inevitably “makes simple observation ineffective”. Indeed, they are not alone in experiencing these challenges. One clever way of their getting round this was the development of a technique for detecting potential level-based and scope-based anomalies in web apps through the analysis of regular database activity as captured in logs.

Typical concurrency analysis begins with a concrete history and a reasoning about why the anomalies that occur within have done so; the novel approach from the Stanford duo instead begins with a concrete trace and generalizes from there to detect possible concurrent interleavings of the operations in the traces. As this leads to an infinite set of potential traces, Warszawski and Bailis then introduced the idea of an abstract history representing in finite space every single expansion of a given trace.

They write, “We developed a new, cross-platform methodology for detecting potential level-based and scope-based anomalies in web applications by analyzing logs of typical database activity. We call this approach Abstract Anomaly Detection (2AD).”

Industry blogger Adrian Colyer describes this as “an incredibly useful analysis tool even if you’re not interested in crafting (or defending against) ACIDRain attacks”.

Warszawski and Bailis ultimately used several methods to detect the potential for ACIDRain attacks, including:

  • The extension of the theory of weak isolation to analyze latent potential for non-serializable behavior under concurrent web API calls;
  • Anomaly Detection (2AD), which they summarize as “the introduction of a language-agnostic method for determining potential isolation anomalies in web applications”, which “deploys dynamic traces of database accesses to efficiently reason about the space of possible concurrent interleavings”;
  • The application of a prototype 2AD analysis tool to 12 self-hosted eCommerce applications written in four languages.

The team used the 2AD prototype to focus on three critical sets of invariant that are shared by almost all popular eCommerce applications:

  • the inventory invariant – each eCommerce site keeps its own bookkeeping of store inventory and each product has a stock value that is removed upon order completion. A product’s stock must be non-negative, and an item’s final stock should reflect the number of orders placed for that item.
  • the voucher invariant used to limit overspending on gift cards, which 9 out of 12 applications enabled
  • the cart invariant, which says that the total amount charged for an order should always reflect the total value of goods in the order. The authors write, “While this invariant may seem obvious, we found that in several of the applications it was possible to add an item to the cart concurrent with checkout, resulting in the user paying for the original total of items in the cart, but placing a valid order including the new item as well. This allows users to obtain items for free. For example, a user might buy a pen and add a laptop to their cart during checkout, paying for the pen but placing an order for the pen and laptopThus, violations of this invariant essentially allow customers to steal items from the store”.

ACIDRain in the Wild: Why Should we Care?

After tracking the invariants across tables and columns of interest, the 2AD prototype delivered a median of 37 witnesses per application. Across the 12 applications, the researchers identified 22 critical types of ACIDRain attack: 9 inventory vulnerabilities, 8 voucher vulnerabilities and 5 cart vulnerabilities. Five were level-based anomalies while the remaining seventeen were scope-based. According to the researchers, “the prevalence of scope-based vulnerabilities even in the presence of transactions indicates that either programmers, ORMs, or both find it difficult to properly use transactions to encapsulate critical operations”. Some applications didn’t use transactions at all while others only used them “sparingly”.

The biggest reason to care about ACIDRain attacks is that 50% of eCommerce sites (over 2 million sites) are at risk. Over 60% of the most popular 1M eCommerce sites are backed by self-hosted eCommerce platforms. Companies using these applications include Lowe’s, The Container Store, Coca-Cola, Ford, Keurig, the British Red Cross, PepBoys and The Piano Guys. As the researchers note, the majority of other eCommerce sites are hosted. Sites such as Squarespace and Shopify provide eCommerce-as-a-service. While they do not directly expose database access, instead they use surface application APIs on the public Internet. Thus, the researchers reason, “it is possible that these hosted eCommerce offerings are subject to the exact same vulnerabilities that many of their self-hosted peers exhibit in our study. One could attempt an attack on these hosted offerings by performing concurrent requests to a store hosted on a platform like Squarespace or Shopify using publicfacing APIs. However, we have not attempted to do so and only report on self-hosted applications here”.

As mentioned above, bitcoin currency exchange Flexcoin was shut down in March 2014 as a result of the exploitation of ACIDRain attacks. All coins in the hot wallet were taken. According to Flexcoin, “By sending thousands of simultaneous requests, the attacker was able to ‘move’ coins from one user account to another until the sending account was overdrawn, before balances were updated”.

The researchers reported 18 vulnerabilities directly to application developers through opening support tickets on the appropriate GitHub repository or issue tracker. They found that there was a mix of responses from the developers involved, revealing different levels of understanding of the threat posed by ACIDRain attacks. Four vulnerabilities had already been noted by other users (although for data corruption not security-related concerns). At the time of the paper, seven reported vulnerabilities had been confirmed.

Overall, the researchers write, “We believe that the magnitude and the prevalence of these vulnerabilities to ACIDRain attacks merits a broader reconsideration of the success of the transaction concept as employed by programmers today, in addition to further pursuit of research in this direction. Based on our early experiences both performing ACIDRain attacks on self-hosted applications as well as engaging with developers, we believe there is considerable work to be done in raising awareness of these attacks—for example, via improved analyses and additional 2AD refinement rules (including analysis of source code to better highlight sources of error)—and in automated methods for defending against these attacks—for example, by synthesizing repairs such as automated isolation level tuning and selective application of SELECT FOR UPDATE mechanisms. Our results here—as well as existing instances of ACIDRain attacks in the wild—suggest there is considerable value at stake”.

Digiprove sealCopyright secured by Digiprove © 2018