Database Transactions – Fraud, Security and the “Halloween Problem”

database transaction is a sequence of operations performed as a single logical unit of work. A logical unit of work must exhibit four properties, called the atomicity, consistency, isolation, and durability (ACID) properties, to qualify as a transaction. [1]

A transaction must be an atomic unit of work; either all of its data modifications are performed, or none of them is performed.

When completed, a transaction must leave all data in a consistent state. In a relational database, all rules must be applied to the transaction’s modifications to maintain all data integrity. All internal data structures, such as B-tree indexes or doubly-linked lists, must be correct at the end of the transaction.

Modifications made by concurrent transactions must be isolated from the modifications made by any other concurrent transactions. A transaction either recognizes data in the state it was in before another concurrent transaction modified it, or it recognizes the data after the second transaction has completed, but it does not recognize an intermediate state. This is referred to as serializability because it results in the ability to reload the starting data and replay a series of transactions to end up with the data in the same state it was in after the original transactions were performed.

After a transaction has completed, its effects are permanently in place in the system. The modifications persist even in the event of a system failure.

The Flexcoin Fraud case study [2]

What happened?

Flexcoin was a Bitcoin exchange that shut down on March 3rd, 2014, when someone allegedly hacked in and made off with 896 BTC in the hot wallet.
The attacker successfully exploited a flaw in the code which allows transfers between flexcoin users. 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. [2]

What was the database flaw that allowed the fraud to take place?

Consider the following as a simplified version of code which dispenses cash from the ATM-

mybalance =“account-number”)  //reads current balance
newbalance = mybalance – amount                   //calculate new balance after ATM withdrawal
database.write(“account-number”, newbalance) //writes new balance into account
dispense_cash(amount)                                  //gives the amount to the user

Now, consider what would happen if a user duplicated his debit card, gave it to his best friend, synchronized their watches, and performed withdrawals at two different ATMs at the same time.

Nothing unexpected would happen, as you’ve probably guessed. And this is because the banks use ACID-compliant databases.

But in the case Flexcoin, it used a NoSQL database – MongoDB. If you recall in our discussions in the NoSQL threads, NoSQl databases are not ACID-compliant, and their strengths lie more in being able to handle Big Data.

Maintaining ACID transactions in not their priority.

This very database transaction flaw (or “feature”) was exploited and was instrumental in the execution of this fraud.

Multiple simultaneous withdrawals were made, and a more money than was is in the account was withdrawn, without the database being any wiser.

Transaction Security [1]

SQL programmers are responsible for starting and ending transactions at points that enforce the logical consistency of the data.
The programmer must define the sequence of data modifications that leave the data in a consistent state relative to the organization’s business rules.
The programmer includes these modification statements in a single transaction so that the SQL Server Database Engine can enforce the physical integrity of the transaction.

It is the responsibility of an enterprise database system, to provide mechanisms ensuring the physical integrity of each transaction.
The Database Engine provides:

  • Locking facilities that preserve transaction isolation.
  • Logging facilities that ensure transaction durability. Even if the server hardware, operating system, or the instance of the Database Engine itself fails, the instance uses the transaction logs upon restart to automatically roll back any uncompleted transactions to the point of the system failure.
  • Transaction management features that enforce transaction atomicity and consistency.
    After a transaction has started, it must be successfully completed, or the instance of the Database Engine undoes all of the data modifications made since the transaction started.

The “Halloween Problem” [3]

What is it?

Back in 1976, Don Chamberlin and Pat Selinger came across a unique problem.
It just so happened that without protection, a query could continue forever (or give results you did not expect).

A Database transaction query to give a 10% raise to everyone that earns less than $25,000 was written and executed-


Seems simple enough but back in 1976 when System R was still a research project, this statement resulted in everyone being given a salary of at least $25,000.

That is, after the update ran, anyone that was previously making <$25k was now making $25k (it updated every row <25k over and over again until they made $25k then stopped).

This problem happened to be discussed with the development team on Halloween day and thus became known in the industry as the “Halloween Problem“.

How could it happen?

If you’re scanning an index on salary (starting with the lowest salary value) and every time you find one that is less than 25000 you update that value by 10%.

You read in the data page and update the salary value and then you have to update the index value.

But since the index is a B+ tree, the update moves the key further down in the index.

Then you continue scanning the index to update more rows.

The problem is that if you move an index key across the index tree, you had better make sure that you don’t see this row again as you continue to scan the index.

That’s what was happening in this case above.
Every time the salary value was updated it would move to the right in the index tree and it would then be seen again and update again, and again and again. Until the value was >= $25000 at which point it would fail the predicate evaluation and it would stop processing.

The database transactions were clearly not ACID and allowed this “problem” to occur.