What Does This Test Actually Prove?

A software engineer's job is not done when the code is written. Equally important is verifying that the code performs as expected. There are various strategies for testing software. Separately, each can find different gaps in the implementation. Together, they can provide even greater confidence in the system. Furthermore, applying insights from real-world deployments can improve the effectiveness of some of these strategies.

Illustrating how different testing strategies are used in the context of a real system can help highlight what each contributes. Consider a pipeline that accepts an arbitrary stream of binary data. It attempts to determine the file format that's encoded in the stream, such as ZIP or PNG, and parse it into a structured form. The data crosses a trust boundary, so it should be treated as untrusted by the parsers. This article will examine the testing of a ZIP parser, from verifying its behavior in isolation through post-deployment monitoring.

Verify the Functionality

It's important to verify that the ZIP parser behaves as expected. Unit tests allow the targeting of individual behaviors directly. In the case of a ZIP archive, it would be prudent to test each of the compression algorithms (e.g., stored, deflate) individually on a data stream.

Writing tests might give insight into parts of the code that are too complex or coupled. For example, while adding tests to the ZIP archive, each compression algorithm was originally coupled within the parsing logic. This made it difficult to test compression edge cases because they required embedding within a valid ZIP archive. Refactoring each compression algorithm into its own class simplified testing these edge cases and made adding support for additional algorithms easier. After this refactoring, a truncated deflate stream or invalid deflate headers could be tested directly instead of also requiring embedding within a full ZIP archive.

Having implementation knowledge will help identify edge cases that should be exercised with targeted tests. A useful but imperfect proxy is code coverage. Each test is only as valuable as what it is asserting. Code coverage cannot measure this. For example, if a corrupt compressed byte stream is used in a test, the error branches will be covered in the coverage report, but the behavior could still be wrong if the test isn't asserting an error. While code coverage is a good guide, it is not sufficient.

After gaining confidence that the ZIP parser behaves according to expectations, the next thing to do is to verify it behaves correctly in the broader system. End-to-end tests should send ZIP archives through the file processing pipeline and validate the processing outputs. The main task is to identify representative ZIP payloads and add them to these tests. Since the unit tests already give confidence that the ZIP parser behaves as expected, it's unnecessary to exhaustively test different permutations of ZIP archives at this level too. A small representative set (e.g., a ZIP archive containing a single file, a ZIP archive containing multiple files, and a corrupt ZIP archive) will provide a substantial amount of confidence at this level. If there are any other unusual integrations, there should also be individual tests for those. These tests are primarily concerned with the correct integration of the ZIP parser and should be written independently of the specific implementation.

At this point, there is a high level of confidence that the code performs as expected both individually and as part of the larger system. Both unit tests and end-to-end tests are types of functional tests that verify behavior. The important qualifier is that this only holds for scenarios envisioned by the developer and tester. The real world might introduce other scenarios that lead to real bugs or crashes.

Verify the Resilience

Fuzz testing (fuzzing) increases confidence that a system behaves safely when given unexpected data. It's unlikely that every potential edge case was imagined and tested during functional testing. For example, the functional tests should validate an error is raised when the ZIP parser is passed a ZIP archive with an invalid compression method. From a functional perspective, any invalid compression method seems like it should be treated like any other, so one test seems like enough. If there is a specific invalid compression method that causes a different class of error due to a bug, it's unlikely to be the invalid compression method used in the functional tests.

Fuzzing stresses a system by sending it lots of variations of data. There are three fuzzing approaches to consider for the ZIP parser:

1. Completely unstructured: Sends a randomized unstructured byte stream to the pipeline. This is useful for testing how the pipeline handles random inputs, which is important since it is required to accept untrusted data that could be anything. In most cases, this stream will not match any parsers, so it is not very useful in stressing them.
2. Partially unstructured: Sends a known byte stream, randomly modified, to the pipeline. The known byte stream can be one of the ZIP archives used in functional testing. As long as the ZIP archive signature remains, the stream will be passed to the ZIP parser and exercise it. Since the generated data is based on a finite input set, it will only be able to produce data similar to that initial set.
3. Structured: Sends a randomized structured byte stream to the pipeline. The fuzzing tool is given a template of a ZIP archive. Depending on the tool, this template could be built declaratively or inferred from a set of representative files. This allows it to generate randomized byte streams that conform to the ZIP archive format. These will be passed to the ZIP parser and exercise a broader and deeper set of code branches.

The list is ordered from easiest to hardest to set up. Code coverage can approximate the thoroughness of each fuzzing approach. Structured fuzzing will touch a larger percentage of the ZIP parser's implementation than the other types. For example, structured fuzzing identified a handful of severe issues in the ZIP parser. These included integer overflow from adding manipulated relative offsets and buffer overruns from offsets pointing past the end of the ZIP archive.

Fuzzing typically runs for hours or days. Whenever unexpected failures or crashes are detected, the byte stream causing the violation is archived for later diagnosis. Confidence increases as fuzzing exercises a broader range of inputs without discovering new failures. While production can always introduce its own wrinkles, confidence at this stage allows the system to be deployed into production.

Verify the Deployment

After deployment, it's important to monitor real usage. Production alerting and crash analysis are outside the scope of this article. Instead, the focus will be on collecting real-world usage data and using that to improve the product.

The file processing pipeline was instrumented with counters to obtain real-world usage statistics. Since the main purpose of the pipeline is to identify and parse binary data streams, it was important to know what types of files were being seen in the real world. This data helped prioritize the list of additional file parsers to add.

The performance monitoring system being used only allowed 64-bit integral key values. The pipeline could identify a large number of file types, so it was easy to map an enum value to an integral key value. Performance counters were added to count the occurrences of each file type. This data was collected and uploaded regularly. Unfortunately, after receiving the initial data, it became clear that this was insufficient. A plurality of files were simply in the "unknown" bucket, which was not helpful.

In order to combat this, a simple two-way encoding was used to map a file extension into an appropriate key. The next deployment allowed collection of both file type (identified by byte stream inspection) and file extension (extracted from the filename). The number of "unknown" files decreased substantially. One interesting finding was a significant increase in the number of PLIST files for a few months, which was likely due to an Apple operating system update.

With this real-world data about file types and extensions seen in the wild, the performance test corpus was updated. Originally, it had contained a fairly equal distribution of file types. With the real-world data, it was tuned to more closely match the real-world distribution. Using the new corpus allowed performance testing that more closely aligned with workloads observed in production. This led to a reordering of optimization priorities. Many of the hot paths that showed up when using the original corpus (e.g., ZIP deflate performance) were less significant when using the new data-driven corpus. Changing the corpus to reflect production workloads changed the conclusions produced by the performance tests.

Conclusion

Testing is just as important to software development as writing code. A well-engineered system doesn't just run. It satisfies its design expectations. There are uncertainties around a code-complete software system:

1. Does the system work as expected and designed?
2. Does the system handle unexpected inputs resiliently?
3. Does the system behave in production as modeled?

At every stage, during and after development there's an opportunity to reduce uncertainty by applying one or more testing strategies. Unit testing and end-to-end testing reduce uncertainty around the system functioning correctly. Fuzz testing reduces uncertainty around the system failing on unexpected inputs. Production monitoring reduces uncertainty around real-world usage and workload assumptions.

Importantly, each testing strategy will provide better results when paired with inputs targeted to the question being asked. Functional testing is best paired with representative success and failure files, specially crafted to exercise known edge cases. Fuzz testing benefits from unexpected and pathological inputs that exercise behavior outside the targeted functional tests. Real-world statistics obtained through performance monitoring can also be used to inform improvements to both the product and its testing. For example, performance testing is most realistic when using a corpus that closely mirrors real-world customer workloads. Applying real-world prevalence data can help build and evolve this corpus.

Each test has a purpose and helps reduce uncertainty. It provides evidence about a particular question under particular conditions. Together, a verification strategy composed of different types of tests can provide evidence about different questions and reduce multiple sources of uncertainty. Confidence comes with understanding what is and isn't out of scope of the strategy.