Notes on Dynamic Program Analysis for Fun and Profit

This post gives an introduction to Dynamic and Static Analysis and also summarizes points discussed in the Mentorship Session: Dynamic Program Analysis for Fun and Profit talk by Dmitry Vyukov part of the Linux Live Mentorship Series. All the images used in this blog post can be found in Author's slide deck as linked here.

Static Program Analysis

Static Program Analysis is the method of detecting bugs without executing the code, instead just by analyzing program code. Static Analysis holds true on all possible execution at once. Some attributes of Static Analysis are:

1. Identifies relatively simpler bugs
2. Provide more Code Coverage
3. Faster and Deterministic Feedback

Since Static Analysis does not depend on the execution of code it only analyzes one uniform configuration among (2^n + different architecture changes) configurations possible, where n represents various configuration variables in the make file.

One of the cons of using Static Program Analysis is the large number of False Positive bugs it reports.

False Positive: a test result that indicates that a bug exists even though the pointed out issue is not exactly a bug

Dynamic Program Analysis

Dynamic Program analysis is the method of detecting bugs by analyzing the properties of a running program. Properties might hold true for a single execution. Some of the properties that are being analyzed are:

1. Performance (Speed or Memory Consumption)
2. Code Coverage (the tool for this purpose is Unit tests)
3. Call Graph: to understand if its possible to get from function A to function B and how exactly we can do that.

Some of the attributes of Dynamic Analysis are:

1. It generally finds more complex Bugs
2. It finds many more True Positives bugs and no false positives
3. Simpler Usage Model

True Positive is a case when the system correctly predicts if there is a bug.

How can we get more test coverage in dynamic analysis:

1. Write better tests(Units or Tests)
2. Use Fuzzing Tool(For Linux Kernel the possible option is to use Syzkaller)
3. Enable Dynamic Analysis while debugging a subsystem of a complex program(such as Linux Kernel).
4. Enable Dynamic Analysis while Dogfooding
5. Sometimes it might be beneficial to enable Dynamic Analysis in Production(bugs that occur in high load cases).

Some of the upstream testing frameworks used are:

• KUnits
• Kselftests (present in tools/testing/selftests)

Using Macros such as BUG_ON and WARN_ON

Macros such as BUG_ON and WARN_ON can be used to check whether a condition is true at runtime. These conditions will be checked for all architectures out there(for now and for the future). Therefore, comments made for these macros are very reliable since they are true for all possible execution cases.

KASAN (KERNEL ADDRESS SANITIZER)

Before we understand what kind of bugs do KASAN catches, we need to also understand, what are the principles of a Dynamic Tools:

1. It should not report any False Positive bugs, even if it comes at the cost of not reporting True Positive Bugs
2. Should be easy to setup
3. Should provide enough information to fix the bug
4. Dynamic Analysing tool should have low overhead, and should not interfere with the kernel/driver tools.

KASAN is enabled via CONFIG_KASAN=Y and can detect:

• Out of Bound errors
• Use after-free bugs
• Bugs on Heap, Stack, and global variables

// Out of bound bug
p = malloc(10);
p[20] = 1;

// Use after free bug
free(p);
p[0] = 1;

The importance of KASAN can be determined by the fact that upon an operation that corrupts memory we would expect our program to crash, however, in reality, it doesn't. So KASAN is a tool that purposely makes the program crash in such instances.