Clang's static analyzer should be able to warn when memset()/memmove()/memcpy() are optimized away by dead store elimination

[ryao]

memset() is often used for data sanitization in encryption code. In a project that I regularly scan with Clang's static analyzer, we recently found some memset() operations meant to protect against information leaks in encryption code were optimized away by dead store elimination.

The optional security.insecureAPI.DeprecatedOrUnsafeBufferHandling (C) check will warn about any usage of memset()/memmove()/memcpy(), but this seems extreme since there are no safe alternatives to memmove()/memcpy() and for initialization, memset() is perfectly safe to use. It would be more useful if a check were made that warns whenever dead store optimization should eliminate a memset()/memcpy()/memmove() operation. The commercial static analyzer, PVS Studio, already does this, but it is prohibitively expensive for open source projects.

https://pvs-studio.com/en/docs/warnings/v570/

[llvmbot]

@llvm/issue-subscribers-clang-static-analyzer

[haoNoQ]

Yes that's a very reasonable check to have (MSC06-C. Beware of compiler optimizations). It sounds like after many years, this is still a real issue.

It requires an analysis technique that the static analyzer isn't exactly built for, as it requires reasoning about all possible execution paths in the program (proving that the write is dead on all paths). Because the engine doesn't have any completeness guarantees, the checker can't rely on the engine to produce such proof, so it's largely on its own. The only checker we have of this kind is the "dead stores" checker, and it's pretty obscure and fairly hard to duplicate. So I think this is a good candidate for the new FlowSensitive engine that's being brought up recently in clang, specifically to deal with these issues (cc @ymand). Also somewhat relevant to the ClangIR effort, as it's a nice borderline example where bug-finding meets optimizations (cc @bcardosolopes).

Side note, it's probably a bad idea to have the static analyzer checker talk to the LLVM optimizer. The LLVM optimizer is highly upredictable and you probably don't want analysis output to depend on -O levels; that's a known anti-pattern in compiler development, you'd rather know about a potential problem regardless of the current optimization level.

The optional security.insecureAPI.DeprecatedOrUnsafeBufferHandling (C) check will warn about any usage of memset()/memmove()/memcpy(), but this seems extreme since there are no safe alternatives to memmove()/memcpy() and for initialization, memset() is perfectly safe to use.

This check seems to actively recommend memset_s() et. al. when they're available (i.e. under C11): https://godbolt.org/z/dYPbbEh77

<source>:4:5: warning: Call to function 'memset' is insecure as it does not provide security checks introduced in the C11 standard. Replace with analogous functions that support length arguments or provides boundary checks such as 'memset_s' in case of C11 [security.insecureAPI.DeprecatedOrUnsafeBufferHandling]

They both cannot be optimized out, and also provide additional bounds safety through the extra parameter, but are otherwise more or less identical. I'm really curious what you think about that alternative, like is it applicable in your case, or does it still look like an overkill in most situations?

[ryao]

They both cannot be optimized out, and also provide additional bounds safety through the extra parameter, but are otherwise more or less identical. I'm really curious what you think about that alternative, like is it applicable in your case, or does it still look like an overkill in most situations?

In the case of OpenZFS, it is written using C99, which does not have memset_s(), and the OpenZFS repository switched from C89 to C99 around 2016, so I would not expect it to be upgraded to a newer version of C for quite some time. Even if we ignore that, OpenZFS is highly portable, with the source code in the main repository being designed to be compile to run in userland (mostly to aid debugging), the Linux kernel and the FreeBSD kernel. The original upstream was illumos, which is a continuation of OpenSolaris. The way we support all of these ports is basically emulating the OpenSolaris API, which will never get memset_s(), although maybe illumos will. That also makes it possible to bring changes from the OpenZFS repository into illumos. Work in progress ports to Windows and MacOS are both in development and will be merged into the main tree eventually. In short, we simply cannot use memset_s() in OpenZFS. Addressing this required that I roll my own solution. Perhaps that could be replaced with a shim in the future, but that depends on what the various platforms we support do.

I consider advice to unconditionally replace memset() with a secure version to be overkill. Replacing memset() with a secure version in the case of initialization unnecessarily slows down software without any security benefit when the compiler determines that writing from a zero register to a memory location can replace the memset() call, or that the zeroed data is always overwritten, so the memset() call can be avoided entirely. The inclusion of memmove()/memcpy()/memset() in security.insecureAPI.DeprecatedOrUnsafeBufferHandling also probably does more harm than good, because most people likely avoid running the check due to all of the complaints it will generate about those three functions. I know that I do. Beyond that, it occurs to me that some people will undoubtably swap the destsz and ch parameters for memset_s(), which could make advice to adopt it do more harm than good among the few that actually listen to that check. :/

I would prefer to see warnings from uses that are almost certainly unsafe, such as when a program zeros stack memory right before a function returns, which will cause dead store elimination to remove memset(). I realize this is easier said than done, especially since marking functions static inline means that you need to consider the callers to know whether a dead store elimination pass would remove memset(). LTO also further complicates things.

[ADKaster]

memset_s is an Annex K function. Annex K is not implemented by any popular Linux C library that I'm aware of. I only know of Microsoft and Wind River to have it implemented. The recommendation to use its functions seems very strange given it's unpopularity with implementers.

[haoNoQ]

Aha, yeah, then I guess it was the right call to make it an off-by-default check. If people actually have them, they can enable it.

I realize this is easier said than done, especially since marking functions static inline means that you need to consider the callers to know whether a dead store elimination pass would remove memset(). LTO also further complicates things.

I suspect that this is somewhat irrelevant to the problem at hand. Pretty much any memset() invocation can be optimized in weird ways, but we don't intend to warn on every memset() invocation because of that. The problem we've identified is that the developer uses this memset() with the intention to securely erase the buffer. If we can somehow prove the developer's intention, at least in some cases, then it'd be sufficient for us to emit a valuable warning.

And one way to prove the developer's intention is to prove that the memset() call literally cannot serve any other purpose. In this case it either serves no purpose at all (dead code - a defect on its own), or it serves the security hardening purpose (again, a defect on its own). So even though we didn't find out which one it is, we know for a fact that the code doesn't make sense. That's a fairly common approach to problems in static analysis: we don't try to predict what the correct fix is, we simply try to point out that no matter how you look at it, the code under analysis doesn't make sense.

So I think this could be a quite reasonable source-based or ClangIR-based flow sensitive check this way.

[ryao]

If it helps, CodeQL already has a check for this. The CodeQL check is open source, so it could probably be skimmed for ideas. CodeQL had been run on OpenZFS PRs, but unfortunately, it failed to catch the issue in OpenZFS because the memset() calls were in a function marked static inline that had been called by the function that did the stack allocation. There is an open CodeQL issue for this:

github/codeql#12352

The vulnerable OpenZFS code probably could be the basis for a test case for a checker. The issue was in both aes_decrypt_atomic() and aes_encrypt_atomic() when calling the static inline function gcm_clear_ctx(), which called memset() to sanitize what was stack memory right before the stack frame containing it would be deallocated. I had confirmed that GCC's dead store elimination would optimize those memset() calls away. I did not look at what LLVM/Clang did, since showing that one compiler's dead store elimination removed those memset() calls was enough to prove to the rest of the project's contributors that I had found a genuine issue. The following are the commit that attempted to sanitize things, but did it improperly, and the commit to fix that oversight respectively:

openzfs/zfs@f58e513
openzfs/zfs@d634d20

[haoNoQ]

Yeah it looks like interprocedural analysis would still be useful for finding some of those bugs. In order to find this specific bug, the checker needs to realize that gcm_clear_ctx() is "a" memset function (its only purpose is to overwrite certain buffers with data, so if it's a dead store, this means that it's definitely just clearing sensitive information), and build a summary of what specifically it memsets (a few buffers behind the ctx parameter).

This sounds quite advanced, so I wouldn't expect us to implement something of this kind quickly. IIUC there are no plans for the FlowSensitive framework to provide generic support for interprocedural analysis. And the static analyzer's generic path sensitive interprocedural analysis can't be used because the problem is not path-sensitive. It's not that hard to build interprocedural flow-sensitive analysis specifically for this problem, but we're not sure whether this is the way we want to go (do we really want to build a custom solution for every checker? so, have a hundred competing solutions to a very non-trivial problem?) so it's a tough call.

But in any case, covering the basic case of plain memset() at end of function may still help find some bugs.

[ryao]

In the short term, it might be wise to make security.insecureAPI.DeprecatedOrUnsafeBufferHandling configurable at the level of individual functions since the sheer number of pointless warnings from its current form do more harm than good by making people disable the check. It appears to be on by default in clang-tidy, which could result in a number of developers avoiding clang-tidy.

Upon deeper inspection, the security.insecureAPI.DeprecatedOrUnsafeBufferHandling check itself has additional problems beyond being noisy on safe uses of the extremely commonly used memset(), memcopy() and memmove() functions. In specific, I spot 3 more commonly used functions on which safety could be more thoroughly analyzed to prevent a flood of pointless warnings:

sscanf() is only unsafe when reading strings unless %*s is used. That can be combined with %n to allow for a copy to be done directly on the substring based on the output of sscanf(). Complaining about sscanf() when it is not printing to a string is counter productive.

Unless you are using the output of snprintf() to advance a pointer to a buffer that will be used for a subsequent write without a bounds check, it is a safe function. The main unsafe use is as part of a loop where the output is used to increment the pointer given to snprintf() while decrementing the buffer size. It would be preferable for the static analyzer to implement a check for that like CodeQL does rather than complain unconditionally:

https://github.com/github/codeql/blob/main/cpp/ql/src/Likely%20Bugs/Format/SnprintfOverflow.ql

That is not to mention that you can do unsafe loops with the "safe" strlcat() and strlcpy() functions, but there is no complaint about them. A file in FreeBSD even implements strlcpy() as #define strlcpy(d,s,n) snprintf((d),(n),"%s",(s)).

I should note that it is possible to figure out the maximum length of the string that would be written by a loop that feeds the output of snprintf() into itself to successively print and allocate a sufficiently large buffer in advance. CodeQL will unconditionally complain about snprintf()'s output being used to advance a pointer passed to it inside a loop. Honestly, it is non-obvious whether that is done to a human programmer, so simply complaining whenever snprintf() is used in that is enough.

The complaint about sprintf() is understandable, but there are ways of using sprintf() that are provably safe. In OpenZFS, we have a number of uses of sprintf() that look like this:

char name[MAXPATHLEN];
sprintf(name, "%llu", (u_longlong_t)guid);

This is provably safe since the maximum possible length string printed is always written to a buffer that is more than adequate to store it. Since the buffer is stack allocated, the static analyzer should be able to determine that this usage is safe.

I did an audit of the OpenZFS codebase not that long ago and switched all unsafe uses of sprintf() to snprintf(). I also switched all potentially unsafe uses of snprintf() to use a custom kmem_scnprintf() function. The function is a wrapper around snprintf() that will return 0 when the buffer is zero or the buffer length - 1 character when an overflow occurs. Switching the unsafe uses of snprintf() to that made them safe. The result is that all complaints by this check about sprintf() on the codebase are noise. It would not be so bad if it only complained in places where it cannot determine that the sprintf() call is safe, but it does not even try to do the most basic check for safety and thus it generates ridiculous numbers of complaints about safe uses.

That said, if you are printing a floating point or double value, the worst case size can be over 300 characters in length, which few developers expect. Coincidentally, CodeQL also has a check for this:

https://github.com/github/codeql/blob/main/cpp/ql/src/Security/CWE/CWE-120/OverrunWriteFloat.ql

Calculation of the worst case buffer usage by a clang static analyzer check should take that into account.

These remarks probably also apply to the v variations of those functions. In specific, vsprintf(), vsscanf() and vsnprintf(), although complaints on those are understandable since figuring out whether they are safe would require CTU, and if they are used in library functions called by other software, then unsafe uses would be hidden from the static analyzer.

[setharnold]

Hello, I do a lot of very quick looks at a wide variety of programs and have a few thoughts to add; if they're not very useful or applicable then I'm sorry for the trouble.

• Reporting on every gets() in a C program is probably useful.
• Reporting on every memset(), memcpy(), and memmove() in a C program is not useful: the ratio of false positives to useful positives is just too high.
• Heuristics that can suggest when dead-store-elimination have removed a memset() would probably be helpful: many projects attempt to zero secrets after use but the memset_s() or SecureZeroMemory() functions aren't available everywhere. So application authors do the best they can with the tools they have and some hints when the compiler elides their work might be helpful for those who try to trick it sufficiently. (Yes, I know that the secret data may still exist in registers or elsewhere in memory, but (a) "write your cryptographic algorithms and protocols in assembly" isn't going to get much traction and (b) exploits that can read memory are far more common than exploits that can read registers.)
• Suggestions to piecemeal replace "dangerous" functions with "safe" functions in an existing codebase is fraught: I've seen more bugs introduced through these attempts than I've seen fixed. Perhaps starting a project with strlcpy() and friends is a good enough idea but I've seen precious few of these, either. The C functions might be horrible but that's what C has and C programmers are used to them. Some help from the compiler to spot unsafe use of them would be amazing. The compiler pointing out use of these functions probably isn't helpful.

Some of the patterns that I think would be far more useful to report:

• char *p = malloc(strlen(foo));
• p = malloc(a * b);
• p = malloc(a + b);
• p = calloc(a * b, c);
• p = calloc(a + b, c);
• p = calloc(a, b * c);
• p = calloc(a, b + c);
• memcpy(a, a+b, c);

These patterns are potentially-unsafe uses of reasonable functions. Actually analyzing them takes time and effort, and I can't expect the compiler to solve the halting problem in an effort to tell the difference. But, some help here would be appreciated.

Thanks

[ryao]

• p = malloc(a * b);

p = malloc(a * sizeof (*p)) should be excluded from such a check. I think there is also an existing check in the static analyzer that catches T1 *p = malloc(a *sizeof (T2)). However, the others make sense to me to report unconditionally.

[setharnold]

On Fri, Mar 03, 2023 at 01:55:43PM -0800, Richard Yao wrote: `p = malloc(a * sizeof (*p))` should be excluded from such a check. I

But if `a` is large enough (which obviously depends upon context) then this multiplication can overflow and allocate vastly less memory than intended. The usual next step is to write `a` objects into the array and stomp all over unrelated memory. `p = calloc(a, sizeof(*p));` would be the usual solution for this case.

[ryao]

On Fri, Mar 03, 2023 at 01:55:43PM -0800, Richard Yao wrote: p = malloc(a * sizeof (*p)) should be excluded from such a check. I
But if a is large enough (which obviously depends upon context) then this multiplication can overflow and allocate vastly less memory than intended. The usual next step is to write a objects into the array and stomp all over unrelated memory. p = calloc(a, sizeof(*p)); would be the usual solution for this case.

Good point, although I would prefer to see a static analyzer check that explicitly checks for the possibility of this issue rather than one that blindly reports every instance of a multiplication. CodeQL has an explicit check for that:

https://github.com/github/codeql/blob/main/cpp/ql/src/Likely%20Bugs/Arithmetic/IntMultToLong.ql

That said, I understand that the Linux kernel has been slowly moving to using helper functions (i.e. kmalloc_array(), kcalloc(), krealloc_array(), struct_size(), array_size() and array3_size()) as a preventative measure instead of relying on static analysis to find such problems. Interestingly, allocations in the Linux kernel will fail long before they reach the sizes that this is a problem (unless they use vmalloc()), so it is a bit odd to see Linux do that, but c'est la vie.

[bcardosolopes]

Very good points raised on this thread! On the clangIR bits mentioned by @haoNoQ

Also somewhat relevant to the ClangIR effort, as it's a nice borderline example where bug-finding meets optimizations (cc @bcardosolopes) .... So I think this could be a quite reasonable source-based or ClangIR-based flow sensitive check this way.

Definitely something that can be done as a ClangIR pass, though the hard part is coming up with the proper heuristics / good user experience.

Since ClangIR is decoupled from LLVM IR level optimization, we wouldn't be able to write such warnings/remarks in the current scenario, but probably in one where we'd have written the same optimization on top of clangir, which will likely happen at some point.