Use Echidna to test a smart contract library

On this submit, we’ll present you the right way to check your sensible contracts with the Echidna fuzzer. Particularly, you’ll see the right way to:

• Discover a bug we found throughout the Set Protocol audit utilizing a variation of differential fuzzing, and
• Specify and examine helpful properties in your personal sensible contract libraries.

And we’ll reveal the right way to do all of this utilizing crytic.io, which supplies a GitHub integration and extra safety checks.

Libraries might import threat

Discovering bugs in particular person sensible contracts is critically essential: A contract might handle vital financial sources, whether or not within the type of tokens or Ether, and damages from vulnerabilities could also be measured in thousands and thousands of {dollars}. Arguably, although, there may be code on the Ethereum blockchain that’s much more essential than any particular person contract: library code.

Libraries are doubtlessly shared by many high-value contracts, so a refined unknown bug in, say, SafeMath, might enable an attacker to take advantage of not only one, however many vital contracts. The criticality of such infrastructure code is nicely understood exterior of blockchain contexts—bugs in extensively used libraries like TLS or sqlite are contagious, infecting doubtlessly all code that depends on the susceptible library.

Library testing usually focuses on detecting reminiscence security vulnerabilities. On the blockchain, nonetheless, we’re not so frightened about avoiding stack smashes or a memcpy from a area containing non-public keys; we’re frightened most in regards to the semantic correctness of the library code. Good contracts function in a monetary world the place “code is legislation,” and if a library computes incorrect outcomes beneath some circumstances, that “authorized loophole” might propagate to a calling contract, and permit an attacker to make the contract behave badly.

Such loopholes might produce other penalties than making a library produce incorrect outcomes; if an attacker can power library code to unexpectedly revert, they then have the important thing to a possible denial-of-service assault. And if the attacker could make a library operate enter a runaway loop, they will mix denial of service with pricey gasoline consumption.

That’s the essence of a bug Path of Bits found in an previous model of a library for managing arrays of addresses, as described on this audit of the Set Protocol code.

The defective code seems like this:

/*** Returns whether or not or not there is a duplicate. Runs in O(n^2).* @param A Array to go looking* @return Returns true if duplicate, false in any other case*/operate hasDuplicate(deal with[] reminiscence A) returns (bool) { for (uint256 i = 0; i < A.size – 1; i++) { for (uint256 j = i + 1; j < A.size; j++) { if (A[i] == A[j]) { return true; } } } return false;}

The issue is that if A.size is 0 (A is empty), then A.size – 1 underflows, and the outer (i) loop iterates over your entire set of uint256 values. The inside (j) loop, on this case, doesn’t execute, so we’ve got a good loop doing nothing for (mainly) eternally. After all this course of will at all times run out of gasoline, and the transaction that makes the hasDuplicate name will fail. If an attacker can produce an empty array in the appropriate place, then a contract that (for instance) enforces some invariant over an deal with array utilizing hasDuplicate might be disabled—probably completely.

The library

For specifics, see the code for our instance, and take a look at this tutorial on utilizing Echidna.

At a excessive stage, the library supplies handy capabilities for managing an array of addresses. A typical use case includes entry management utilizing a whitelist of addresses. AddressArrayUtils.sol has 19 capabilities to check:

operate indexOf(deal with[] reminiscence A, deal with a)operate incorporates(deal with[] reminiscence A, deal with a)operate indexOfFromEnd(deal with[] A, deal with a)operate lengthen(deal with[] reminiscence A, deal with[] reminiscence B)operate append(deal with[] reminiscence A, deal with a)operate sExtend(deal with[] storage A, deal with[] storage B)operate intersect(deal with[] reminiscence A, deal with[] reminiscence B)operate union(deal with[] reminiscence A, deal with[] reminiscence B)operate unionB(deal with[] reminiscence A, deal with[] reminiscence B)operate distinction(deal with[] reminiscence A, deal with[] reminiscence B)operate sReverse(deal with[] storage A)operate pop(deal with[] reminiscence A, uint256 index)operate take away(deal with[] reminiscence A, deal with a)operate sPop(deal with[] storage A, uint256 index)operate sPopCheap(deal with[] storage A, uint256 index)operate sRemoveCheap(deal with[] storage A, deal with a)operate hasDuplicate(deal with[] reminiscence A)operate isEqual(deal with[] reminiscence A, deal with[] reminiscence B)operate argGet(deal with[] reminiscence A, uint256[] reminiscence indexArray)

It looks like loads, however most of the capabilities are related in impact, since AddressArrayUtils supplies each useful variations (working on reminiscence array parameters) and mutating variations (requiring storage arrays) of lengthen, reverse, pop, and take away. You possibly can see how as soon as we’ve written a check for pop, writing a check for sPop in all probability gained’t be too troublesome.

Property-based fuzzing 101

Our job is to take the capabilities we’re fascinated by—right here, all of them—and:

• Determine what every operate does, then
• Write a check that makes certain the operate does it!

A method to do that is to write down numerous unit checks, in fact, however that is problematic. If we wish to completely check the library, it’s going to be numerous work, and, frankly, we’re in all probability going to do a nasty job. Are we certain we are able to consider each nook case? Even when we attempt to cowl all of the supply code, bugs that contain lacking supply code, just like the hasDuplicate bug, can simply be missed.

We wish to use property-based testing to specify the final conduct over all doable inputs, after which generate numerous inputs. Writing a basic description of conduct is tougher than writing any particular person concrete “given inputs X, the operate ought to do/return Y” check. However the work to write down all of the concrete checks wanted could be exorbitant. Most significantly, even admirably well-done guide unit checks don’t discover the sort of bizarre edge-case bugs attackers are in search of.

The Echidna check harness: hasDuplicate

The obvious factor in regards to the code to check the library is that it’s greater than the library itself!  That’s not unusual in a case like this. Don’t let that daunt you; in contrast to a library, a check harness approached as a work-in-progress, and slowly improved and expanded, works simply fantastic. Take a look at improvement is inherently incremental, and even small efforts present appreciable profit in case you have a device like Echidna to amplify your funding.

For a concrete instance, let’s take a look at the hasDuplicate bug. We wish to examine that:

• If there’s a duplicate, hasDuplicate reviews it, and
• If there isn’t a replica, hasDuplicate reviews that there isn’t one.

We might simply re-implement hasDuplicate itself, however this doesn’t assist a lot usually (right here, it’d allow us to discover the bug). If we had one other, independently developed, high-quality deal with array utility library, we might evaluate it, an strategy referred to as differential testing. Sadly, we don’t usually have such a reference library.

Our strategy right here is to use a weaker model of differential testing by in search of one other operate within the library that may detect duplicates with out calling hasDuplicate. For this, we’ll use indexOf and indexOfFromEnd to examine if the index of an merchandise (ranging from 0) is similar as that when a search is carried out from the top of the array:

for (uint i = 0; i < addrs1.size; i++) { (i1, b) = AddressArrayUtils.indexOf(addrs1, addrs1[i]); (i2, b) = AddressArrayUtils.indexOfFromEnd(addrs1, addrs1[i]); if (i1 != (i2-1)) } return hasDup == AddressArrayUtils.hasDuplicate(addrs1); }

See the complete instance code in our addressarrayutils demo

This code iterates by means of addrs1 and finds the index of the primary look of every factor.  If there are not any duplicates, in fact, this may at all times simply be i itself. The code then finds the index of the final look of the factor (i.e., from the top). If these two indices are completely different, there’s a duplicate. In Echidna, properties are simply Boolean Solidity capabilities that often return true if the property is happy (we’ll see the exception beneath), and fail in the event that they both revert or return false. Now our hasDuplicate check is testing each hasDuplicate and the 2 indexOf capabilities. In the event that they don’t agree, Echidna will inform us.

Now we are able to add a few capabilities to be fuzzed to set addrs1.

Let’s run this property on Crytic:

First, crytic_hasDuplicate fails:

crytic_hasDuplicate: failed! Name sequence: set_addr(0x0)

The triggering transaction sequence is very simple: Don’t add something to addrs1, then name hasDuplicate on it. That’s it—the ensuing runaway loop will exhaust your gasoline price range, and Crytic/Echidna will inform you the property failed. The 0x0 deal with outcomes when Echidna minimizes the failure to the best sequence doable.

Our different properties (crytic_revert_remove and crytic_remove) cross, in order that’s good. If we repair the bug in hasDuplicate then our checks will all cross:

The crytic_hasDuplicate: fuzzing (2928/10000) tells us that for the reason that costly hasDuplicate property doesn’t rapidly fail, solely 3,000 of our most of 10,000 checks for every property have been carried out earlier than we hit our timeout of 5 minutes.

The Echidna check harness: The remainder of the library

Now we’ve seen one instance of a check, listed below are some primary solutions for constructing the remainder of the checks (as we’ve carried out for the addressarrayutils_demo repository):

• Attempt other ways of computing the identical factor. The extra “differential” variations of a operate you will have, the extra doubtless you might be to search out out if one among them is fallacious. For instance, take a look at all of the methods we cross-check indexOf, incorporates, and indexOfFromEnd.
• Take a look at for revert. In case you add the prefix _revert_ earlier than your property identify as we do right here, the property solely passes if all calls to it revert. This ensures code fails when it’s alleged to fail.
• Don’t neglect to examine apparent easy invariants, e.g., that the diff of an array with itself is at all times empty (ourEqual(AddressArrayUtils.distinction(addrs1, addrs1), empty)).
• Invariant checks and preconditions in different testing also can function a cross-check on examined capabilities. Be aware that hasDuplicate known as in lots of checks that aren’t meant to examine hasDuplicate in any respect; it’s simply that realizing an array is duplicate-free can set up extra invariants of many different behaviors, e.g., after eradicating deal with X at any place, the array will not comprise X.

Getting up and operating with Crytic

You possibly can run Echidna checks by yourself by downloading and putting in the device or utilizing our docker construct—however utilizing the Crytic platform integrates Echidna property-based testing, Slither static evaluation (together with new analyzers not out there within the public model of Slither), upgradability checks, and your personal unit checks in a seamless atmosphere tied to your model management. Plus the addressarrayutils_demo repository reveals all you want for property-based testing: It may be so simple as making a minimal Truffle setup, including a crytic.sol file with the Echidna properties, and turning on property-based checks in your repository configuration in Crytic.

Join Crytic immediately, and in case you have questions, be a part of our Slack channel (#crytic) or observe @CryticCI on Twitter.

*** This can be a Safety Bloggers Community syndicated weblog from Path of Bits Weblog authored by Alex Groce. Learn the unique submit at: https://weblog.trailofbits.com/2020/08/17/using-echidna-to-test-a-smart-contract-library/