Detecting vulnerabilities with the bug hunting

[Daniel Marjamäki]

I wonder if you volounteer to generate some table that we can show on a webpage? I just envision a static html table. I don't know what info we want about each CVE..
Imho.. most important fields are: CVE id and status.
some example statuses:
* not found
* found
* error not handled yet (it's not a uninit/bufferOverflow/divisionByZero)
* unable to determine location/error

[Daniel Marjamäki]

let's skip the webpage for now.. I want to look at the bugs first ..

[Georgiy Komarov]

We can get a list of modified files through Github API too. This allows us to fetch a list of changed files and patches without cloning the repo. And we can generate the commands with Cppcheck start options.

I updated the script, and now it can generate reports in html format. That's what I got.

[Georgiy Komarov]

Interesting, I see some unrelated repositories in the report. For example, CVE-2020-8929 contains bug in the Java code, but the main language of this repository is C++. Some patches also includes changes in tests and build system files. We need to filter out this noise somehow.

[Daniel Marjamäki]

I am looking at the CWE-787 from your tool. Here is a spreadsheet with my notes about each CVE.
https://docs.google.com/spreadsheets/d/1FJWS-rgPGxdj0yx1UDsPbRMP1njtU9cbhewMjuDf0Fw/edit?usp=sharing

All CVEs are listed and I have taken a quick look on each so far.

[Georgiy Komarov]

Okay. I haven't really delved into the implementation of bug-hunting, so I need to read the sources before I can work with these problems in Cppcheck.

As far as I understand, the key idea is to collect symbolic equations from the AST and use z3 to solve them, am I right?

What problems and limitations are currently exists in the current implementation of bug-hunting? What causes the highest number of false positives/negatives? I can suppose that it will be extremely difficult to handle non-pure functions. Especially when they are use some kind of mutable state (e.g. class fields).

[Daniel Marjamäki]

Okay. I haven't really delved into the implementation of bug-hunting, so I need to read the sources before I can work with these problems in Cppcheck.

ok.. feel free to ask..

I think what I want help with mostly right now is to just look at the CVE reports and then try to figure out what the bug in the CVE is and where. No need to look at Cppcheck.

As far as I understand, the key idea is to collect symbolic equations from the AST and use z3 to solve them, am I right?

Yes

What problems and limitations are currently exists in the current implementation of bug-hunting?

That is not well known right now.. I want that we look at CVEs and make an understanding..

Maybe we should have some technical document that describes bug hunting. So people can understand roughly how this works.

Cppcheck bug hunting is not very sophisticated. Cppcheck bug hunting performs a "high level" analysis of your C/C++ code. We use knowledge about the classes, functions and types that are used. It does not perform a full whole program analysis.

If you have this code:

void foo(std::string from) {
    std::string to = from;
}

void bar(const char *from) {
    char to[100];
    strcpy(to, from);
}

In theory these functions foo and bar do more or less the same thing. For a "low level" analysis (for instance: dynamic analysis).. there wouldn't be a lot of difference behind the scenes.

For the function "foo" I can't really imagine what UB there could be. If we know what a std::string is then we can determine that the code is safe. And Cppcheck has this knowledge. So Cppcheck will by design be silent about foo.

For the function "bar", many UB are possible. Buffer overflows for both from and to, null pointer dereference of from, use after free, .. By design, Cppcheck will report all those bugs for bar.

For "vanilla" C code there could be a lot of false positives but the situation can be improved with high level knowledge. If we have an attribute or configuration that says that from must be a zero-terminated string then the only UB I can see is to might buffer overflow. Then whenever bar is called anywhere Cppcheck must enforce that the parameter is a zero-terminated string and if Cppcheck can't determine that then Cppcheck will warn...

The challenge will be to make bug hunting as practical as possible.

[Daniel Marjamäki]

In the "low end" we have embedded safety critical C projects. As far as I know, dynamic memory allocation is often forbidden in these projects. I hope that a well written safety critical C project will probably not generate a lot of noise (however I don't have such code to test on).

In the "high end" we have well written C++ projects. Using containers and smart pointers etc. I believe there will not be lots of noise.

In the "middle ground" we have old style C/C++ code that uses dynamic memory and raw pointers. By design we will write lots of warnings for such code. It should be possible to reduce those warnings with configuration/annotations but it will require work..

[Richard Smith]

In the "low end" we have embedded safety critical C projects. As far as I know, dynamic memory allocation is often forbidden in these projects. I hope that a well written safety critical C project will probably not generate a lot of noise (however I don't have such code to test on).

I do. However, It is not public so I wold have to run it and just report back the results. I have at least one version with a known buffer overflow. I can run against that file. I have never used the bug hunting feature though so I'll need the recipe for how to use it.

[Daniel Marjamäki]

Fantastic! Thanks!

If you compile cppcheck yourself.. you must use USE_Z3=yes during compilation. CMake has some such option also.

I suggest that you run this:

cppcheck --check-config folder/file

Add local include paths that are needed. Now you can run bug hunting..

cppcheck --bug-hunting -I.. folder/file

[Daniel Marjamäki]

For information .. when I run bug hunting on our production code I always use the GUI. It's so much easier to read the results..

[Georgiy Komarov]

Thank you for the detailed explanation. I got the idea.

I think there is a trade-off between accuracy and easy of use of the static analysis tool. On the one hand, we want to make our software as safe as possible, but this will requires us a huge effort to write and maintain the correct annotations. Basically, we need to rewrite the entire project in some kind of DSL for contracts. This approach is applicable in small safety-critical projects, but this is completely unacceptable for typical commercial projects, since it will require much more development time. This approach reminds me of the FramaC framework with their families of annotation languages and overwhelming configuration process. I have not yet met people who would use it in real projects.

On the other hand, we have static analysis tools like Cppcheck, PVS Studio, MathWorks Polyspace etc., that just work. We can install one of these tools on a CI server and handle a number of typical C/C++ errors "for free", without additional configuration.

But I'm not yet completely understand, what the purpose of bug-hunting feature in Cppcheck. Do we wanna be like FramaC, that is, we want to force the user to write contracts for all functions in their code to guarantee them maximum safety? Or may be there are some ways to automate code verification process, or make it less invasive? For example, to perform bug-hunting checking only for a part of the whole code base?

[Daniel Marjamäki]

The bug hunting is not targeted for CI. There will be false positives for working code. I am happy if there are a handful of false positives for each file.

One use case is to just somehow indicate dangerous code while a developer is writing code directly in the editor. I had a work-in-progress where cppcheck would take the output from git diff and only report issues in the changed lines of code. I think it would be possible to configure some of the existing cppcheck IDE plugins to do this already at this moment..

Another use case I envision is when you make a release.. if you tag a "release candidate" and want to perform an extended static analysis on that. You could focus extra attention on warnings related to the new features that has been developed then should not be a lot of false positives to look at. Maybe looking at every warning for each major release is also acceptable..

we want to force the user to write contracts for all functions in their code to guarantee them maximum safety?

No.. it is optional if there are contracts in the code we use them. If there is configuration in the Cppcheck GUI project file then we use that.. we will not force it. You can run without configuration but there will be more noise.

I would not envision that anybody will decorate all their functions with contracts just for Cppcheck. In coming C++ there will be contracts and if such contracts are written I assume various tools and compilers can use them. So it's reasonable to use those in Cppcheck also.

In Windows API there is this typedef: typedef __nullterminated CONST CHAR *LPCSTR;.. so well one approach would be that we define such typedef also and then users can just change bar(char *from) to bar(LPCSTR from). Their compiler will not see a big difference but for Cppcheck it will be an important difference. Of course if they don't like the name in a project they can choose a different name I'd recommend that the typedef is specified in a header.

I think that different projects will want to solve this in different ways.

I run Cppcheck bug hunting on the projects I develop professionally.. it is c++ code. So far I must admit I do not configure a lot myself. I think the noise is manageable for me.

This is intended to be "noisy" but I do not think that all levels of noise is ok. We should fix warnings that can be proven are false positives.

[Daniel Marjamäki]

I think that in the near future.. bug hunting will not be very practical for "middle ground" projects. As you say Georgy we can't for instance force projects to be rewritten..

A "middle ground" C++ project should probably be modernized imho. Containers should be used unless there are good reasons. Encapsulations could make the code easier to analyze and read and less error prone. But well there must be strong motivation to modernize the code it can't only be cppcheck bug hunting.

For a "middle ground" C project -- Cppcheck bug hunting will not be really practical I'm afraid. If they are willing to spend a lot of time looking at noise ...

For "low end" and "high end" projects I hope it's a practical tool..

[Georgiy Komarov]

One use case is to just somehow indicate dangerous code while a developer is writing code directly in the editor. I had a work-in-progress where cppcheck would take the output from git diff and only report issues in the changed lines of code. I think it would be possible to configure some of the existing cppcheck IDE plugins to do this already at this moment..

It probably can be used with git pre-commit hook.

No.. it is optional if there are contracts in the code we use them.

I was running Cppcheck in bug-hunting mode for some of our proprietary projects that are related with low-level networking in mixed C/C++ code. This gave me warnings to literally every function that work with memory in C-style: memcpy, memcmp, etc.

So, I'm wondering, how can we detect false positives in buffer overflow errors without contracts and without launching the program (e.g. dynamic analysis). Where can we get information about the buffer size? Perhaps it makes sense to use abstract interpretation or some other techniques?

[Daniel Marjamäki]

So, I'm wondering, how can we detect false positives in buffer overflow errors without contracts and without launching the program (e.g. dynamic analysis). Where can we get information about the buffer size?

It is a huge problem to be practically useful for such code. I am open for suggestions..

Yes it's the question where we can get the information about the buffer size. There are so many variants..

Perhaps it makes sense to use abstract interpretation or some other techniques?

We do use a simple abstract interpretation. It executes from the top of the function and down. when there are conditions the execution is split up into true/false branches. there is no "join" currently after conditional blocks so it can "explode".

Example code:

1: void foo(short x)
2: {
3:   int a = x;
4:   if (x > 15)
5:       a += 1;
6:   int b = a;
}

Output from cppcheck --debug --debug-bug-hunting --bug-hunting --verbose 1.c:

2:1: $1=-32768:32767
2:1: 0:{ x=$1}
3:13: 0:{ x=$1 a=$1}
5:0: 0:{ x=$1 a=($1)+(1)}
5:0: 1:{ x=$1 a=$1}
5:14: 0:{ x=$1 a=($1)+(1)}
6:13: 0:{ x=$1 a=($1)+(1) b=($1)+(1)}
6:13: 1:{ x=$1 a=$1 b=$1}

line 2: Creates a symbolic value for "x" that has the value -32768:32767.
The "0:{ x=$1}" means: execution path 0 has state { x=$1 }

line 3: After statement is executed, execution path 0 has this state: { x=$1 a=$1}

line 5:
Execution path 0 has this state: { x=$1 a=($1)+(1)}
Execution path 1 has this state: { x=$1 a=$1}

...

The constraint expressions for all branches are also saved in the state but it is not shown here :-(... I should add those..

.. I believe that this abstract interpretation is far from perfect. So if you see false positives please report that...

[Daniel Marjamäki]

In our CVE investigations it doesn't really matter if there are lots of false positives. We know exactly which warning we are looking for. It is good for the confidence to show that we can detect those issues also.. if I don't get those warnings in my code I can relax a bit..

Well I totally agree that we should consider how to make Cppcheck usable for your use case also.. maybe make it possible to turn down the "noise level". We can add some optional specific bailouts if the code might be totally OK.

[Georgiy Komarov]

Got it, thanks for the explanations.

I tried to find some CVEs using bug-hunting feature. It can't be used in practice yet, because the noise level is huge.

CVE-2020-12654 was not detected. It somewhat strange, because there is no warning to memcpy call at all. Here is a link after the fix (comment previous if statement to reproduce CVE).

CVE-2020-10232: false positive bughuntingUninit was generated for the affected lines. This is incorrect, because it does not use information about the buffer size at all, so it doesn't detect overflows here.

[Daniel Marjamäki]

It can't be used in practice yet, because the noise level is huge.

I would be very interested to get your input about what you would consider to be practical approaches in your real project;

• I assume that it is not practical that you would add function countracts throughout the code. Maybe it's even more difficult politically than technically? People would not like it. For information in Cppcheck we have added nonneg here and there and that is checked by the bug hunting, I would guess that a few keywords here and there would be possible politically if you can demonstrate the value.

• You can add configurations in the GUI. You could pick a file or two to start with. As we have a GUI we can try to make this pretty straight forward and quick. For instance if we show your function code and show what symbolic values we create and where and then allow the user to edit our symbolic values directly in the GUI. Or how about generic rules based on type/variable/function name (example: all parameters in the project with the name "pIn" always point at initialized data). Or we could have a dialog where all our assumptions are shown with a check box for each of them and the user can choose to disable arbitrary assumptions. Or...

• A perfect whole program analysis would be sweet .. but I do not see this as a possible solution

[Daniel Marjamäki]

For instance if we show your function code and show what symbolic values we create and where and then allow the user to edit our symbolic values directly in the GUI.

To debug the exprengine can be a bit tricky. You saw the debug output. so well I think it would also help us with exprengine debugging if that output is visualized somehow.

And it might be possible to create a cool looking screenshot :-)

[Georgiy Komarov]

I assume that it is not practical that you would add function countracts throughout the code.

Ah, of course, I'm about open source projects. I'm about the long debug outputs that I got when analyzing those two CVEs.

To debug the exprengine can be a bit tricky. You saw the debug output. so well I think it would also help us with exprengine debugging if that output is visualized somehow.

I'll take a look.

[Daniel Marjamäki]

To debug the exprengine can be a bit tricky. You saw the debug output. so well I think it would also help us with exprengine debugging if that output is visualized somehow.

I'll take a look.

I imagine something like that:

------------------------------------------------
        void foo(short x)
        {
Create symbolic value:  $1=-32678:32767
0: { x=$1}
------------------------------------------------
            int a = x;
0: { x=$1 a=$1}
------------------------------------------------
            if (x > 15)
Split:
0: Constraint added:  $1>15
1: Constraint added:  !($1>15)
------------------------------------------------
                a++;
0: { x=$1 a=$1+1}
------------------------------------------------
0:{ x=$1 a=($1)+(1)}
1:{ x=$1 a=$1}
            return a;
------------------------------------------------
        }

That was a quick pure text hack to give an idea.. I think it should be possible to do some better visualisations in the GUI.

[Daniel Marjamäki]

It might be interesting to show only the effects of a statement. not the full state. if the user can expand it and show the full state.

[Georgiy Komarov]

I implemented this in https://github.com/jubnzv/cppcheck-nvd-checker

Here's a preview:

[Daniel Marjamäki]

interesting.. so the idea in short is to run cppcheck with --debug-bug-hunting read the output and convert that into some html?

It seems to me that the output (debug output from cppcheck) is not really user friendly but it's a good start. We could tweak the debug output from cppcheck.