Results of static analysis with clang static analyser

Results of static analysis with clang static analyser

[Khem Raj]

Hi All

I have run scan-build on musl-git and here are results

http://busybox.net/~kraj/scan-build-2015-09-22-224330-15962-1/

Cheers

-Khem

Re: Results of static analysis with clang static analyser

[Rich Felker]

On Tue, Sep 22, 2015 at 10:58:55PM -0700, Khem Raj wrote:
> Hi All
> 
> I have run scan-build on musl-git and here are results
> 
> http://busybox.net/~kraj/scan-build-2015-09-22-224330-15962-1/

At a quick glance, most of these seem to be cases of assuming system
calls do not store to the objects they receive pointers to. This makes
them false positives, but if llvm is actually making that same
assumption when optimizing that could be a bug in itself. Hopefully
it's just treating it as "unknown" whether the object is stored to,
rather than "definitely not accessed".

I'll look at it in more detail later. Thanks!

Rich

Re: Results of static analysis with clang static analyser

[Jens Gustedt]

[-- Attachment #1: Type: text/plain, Size: 1719 bytes --]

Am Mittwoch, den 23.09.2015, 15:38 -0400 schrieb Rich Felker:
> On Tue, Sep 22, 2015 at 10:58:55PM -0700, Khem Raj wrote:
> > Hi All
> > 
> > I have run scan-build on musl-git and here are results
> > 
> > http://busybox.net/~kraj/scan-build-2015-09-22-224330-15962-1/
> 
> At a quick glance, most of these seem to be cases of assuming system
> calls do not store to the objects they receive pointers to.

Some of them, yes. But the one in __memalign seems to have secret
knowledge that it may access header information preceeding the pointer
that was received from malloc. I have no idea what a compiler in a
freestanding environment is allowed (or not) to assume in that case.

Perhaps it would be cleaner to have a malloc_helper function that
returns the veritable start of the reserved chunk and then the user
interface wrappers such as malloc and friends return that address plus
the necessary offset.

> This makes
> them false positives, but if llvm is actually making that same
> assumption when optimizing that could be a bug in itself. Hopefully
> it's just treating it as "unknown" whether the object is stored to,
> rather than "definitely not accessed".

The one in pthread_create I always struggle with. I remember that I
had myself once convinced (or was it you?) that the bad case can't
happen, but I was not able to reproduce the argument spontaneously.

Jens

-- 
:: INRIA Nancy Grand Est ::: Camus ::::::: ICube/ICPS :::
:: ::::::::::::::: office Strasbourg : +33 368854536   ::
:: :::::::::::::::::::::: gsm France : +33 651400183   ::
:: ::::::::::::::: gsm international : +49 15737185122 ::
:: http://icube-icps.unistra.fr/index.php/Jens_Gustedt ::





[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 181 bytes --]

Re: Results of static analysis with clang static analyser

[Rich Felker]

On Wed, Sep 23, 2015 at 10:02:51PM +0200, Jens Gustedt wrote:
> Am Mittwoch, den 23.09.2015, 15:38 -0400 schrieb Rich Felker:
> > On Tue, Sep 22, 2015 at 10:58:55PM -0700, Khem Raj wrote:
> > > Hi All
> > > 
> > > I have run scan-build on musl-git and here are results
> > > 
> > > http://busybox.net/~kraj/scan-build-2015-09-22-224330-15962-1/
> > 
> > At a quick glance, most of these seem to be cases of assuming system
> > calls do not store to the objects they receive pointers to.
> 
> Some of them, yes. But the one in __memalign seems to have secret
> knowledge that it may access header information preceeding the pointer
> that was received from malloc. I have no idea what a compiler in a
> freestanding environment is allowed (or not) to assume in that case.

malloc is not reserved in a freestanding environment. LLVM/clang used
to get this wrong and badly broke musl, but it was fixed sometime
around 3.4 or 3.5 I think.

> Perhaps it would be cleaner to have a malloc_helper function that
> returns the veritable start of the reserved chunk and then the user
> interface wrappers such as malloc and friends return that address plus
> the necessary offset.

It might, but that probably add an extra layer of call. I'll see if I
can come up with a reasonable way to do something like this when I get
around to overhauling malloc, though, since it seems useful.

> > This makes
> > them false positives, but if llvm is actually making that same
> > assumption when optimizing that could be a bug in itself. Hopefully
> > it's just treating it as "unknown" whether the object is stored to,
> > rather than "definitely not accessed".
> 
> The one in pthread_create I always struggle with. I remember that I
> had myself once convinced (or was it you?) that the bad case can't
> happen, but I was not able to reproduce the argument spontaneously.

From my perspective, this one is simply a bug in the static analysis.
At line 218, pointer arithmetic was performed on `stack` to get `tsd`.
If `stack` were null this would be UB, and if `stack` is not null then
you cannot get a null pointer without the arithmetic having invoked
UB, so you can conclude that `tsd` is not null.

Of course such UB could happen if inputs are invalid (e.g. attribute
containing a size larger than the actual size of the stack) or if
internal state is invalid (e.g. if the computation of `need` wraps),
so maybe it's useful to have this analysis take place.

Rich

Re: Results of static analysis with clang static analyser

[Jens Gustedt]

[-- Attachment #1: Type: text/plain, Size: 1581 bytes --]

Am Mittwoch, den 23.09.2015, 20:34 -0400 schrieb Rich Felker:
> On Wed, Sep 23, 2015 at 10:02:51PM +0200, Jens Gustedt wrote:
> > The one in pthread_create I always struggle with. I remember that I
> > had myself once convinced (or was it you?) that the bad case can't
> > happen, but I was not able to reproduce the argument spontaneously.
> 
> From my perspective, this one is simply a bug in the static analysis.
> At line 218, pointer arithmetic was performed on `stack` to get `tsd`.
> If `stack` were null this would be UB, and if `stack` is not null then
> you cannot get a null pointer without the arithmetic having invoked
> UB, so you can conclude that `tsd` is not null.

I wouldn'd call this a bug. This also assumes that the analyser has do
"know" from somewhere that `stack` is a pointer that is sufficiently
far from the 0 address, so the result of the arithmetic can never be a
0 valued pointer.

So the problem here is that we use a pointer value that is the result
of arithmetic to hold the state of a conditional execution.

AFAICS, we could completely avoid that by placing a goto after line
220 to jump to line 251. Then the initialization of tsd and the `if
(!tsd)` conditional (not the code inside) could be omitted.

Jens


-- 
:: INRIA Nancy Grand Est ::: Camus ::::::: ICube/ICPS :::
:: ::::::::::::::: office Strasbourg : +33 368854536   ::
:: :::::::::::::::::::::: gsm France : +33 651400183   ::
:: ::::::::::::::: gsm international : +49 15737185122 ::
:: http://icube-icps.unistra.fr/index.php/Jens_Gustedt ::




[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 181 bytes --]

[PATCH] help static analysis by avoiding to hold state in a pointer that is subject to arithmetic

[Jens Gustedt]

---
 src/thread/pthread_create.c | 36 ++++++++++++++++++------------------
 1 file changed, 18 insertions(+), 18 deletions(-)

diff --git a/src/thread/pthread_create.c b/src/thread/pthread_create.c
index e7df34a..c00c3fe 100644
--- a/src/thread/pthread_create.c
+++ b/src/thread/pthread_create.c
@@ -181,7 +181,7 @@ int __pthread_create(pthread_t *restrict res, const pthread_attr_t *restrict att
 	int ret, c11 = (attrp == __ATTRP_C11_THREAD);
 	size_t size, guard;
 	struct pthread *self, *new;
-	unsigned char *map = 0, *stack = 0, *tsd = 0, *stack_limit;
+	unsigned char *map = 0, *stack = 0, *tsd, *stack_limit;
 	unsigned flags = CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND
 		| CLONE_THREAD | CLONE_SYSVSEM | CLONE_SETTLS
 		| CLONE_PARENT_SETTID | CLONE_CHILD_CLEARTID | CLONE_DETACHED;
@@ -218,6 +218,7 @@ int __pthread_create(pthread_t *restrict res, const pthread_attr_t *restrict att
 			tsd = stack - __pthread_tsd_size;
 			stack = tsd - libc.tls_size;
 			memset(stack, 0, need);
+			goto setup;
 		} else {
 			size = ROUND(need);
 			guard = 0;
@@ -228,26 +229,25 @@ int __pthread_create(pthread_t *restrict res, const pthread_attr_t *restrict att
 			+ libc.tls_size +  __pthread_tsd_size);
 	}
 
-	if (!tsd) {
-		if (guard) {
-			map = __mmap(0, size, PROT_NONE, MAP_PRIVATE|MAP_ANON, -1, 0);
-			if (map == MAP_FAILED) goto fail;
-			if (__mprotect(map+guard, size-guard, PROT_READ|PROT_WRITE)
-			    && errno != ENOSYS) {
-				__munmap(map, size);
-				goto fail;
-			}
-		} else {
-			map = __mmap(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANON, -1, 0);
-			if (map == MAP_FAILED) goto fail;
-		}
-		tsd = map + size - __pthread_tsd_size;
-		if (!stack) {
-			stack = tsd - libc.tls_size;
-			stack_limit = map + guard;
+	if (guard) {
+		map = __mmap(0, size, PROT_NONE, MAP_PRIVATE|MAP_ANON, -1, 0);
+		if (map == MAP_FAILED) goto fail;
+		if (__mprotect(map+guard, size-guard, PROT_READ|PROT_WRITE)
+		    && errno != ENOSYS) {
+			__munmap(map, size);
+			goto fail;
 		}
+	} else {
+		map = __mmap(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANON, -1, 0);
+		if (map == MAP_FAILED) goto fail;
+	}
+	tsd = map + size - __pthread_tsd_size;
+	if (!stack) {
+		stack = tsd - libc.tls_size;
+		stack_limit = map + guard;
 	}
 
+setup:
 	new = __copy_tls(tsd - libc.tls_size);
 	new->map_base = map;
 	new->map_size = size;
-- 
2.1.4

Re: Results of static analysis with clang static analyser

[Matt Avery]

[-- Attachment #1: Type: text/plain, Size: 1966 bytes --]

I'm not sure how keen you are to use asserts, but adding them helps the static analyzer not evaluate impossible paths. From the docs <http://clang-analyzer.llvm.org/scan-build.html>:

ALWAYS analyze a project in its "debug" configuration

Most projects can be built in a "debug" mode that enables assertions.
Assertions are picked up by the static analyzer to prune infeasible paths, which
in some cases can greatly reduce the number of false positives (bogus error
reports) emitted by the tool.

Adding an assert(tsd != 0) after the arithmetic operation, or even better,  assert(stack > __pthread_tsd_size) before should be enough?  
-Matt



On 09/24/2015 03:22 AM, Jens Gustedt wrote:
> Am Mittwoch, den 23.09.2015, 20:34 -0400 schrieb Rich Felker:
>> On Wed, Sep 23, 2015 at 10:02:51PM +0200, Jens Gustedt wrote:
>>> The one in pthread_create I always struggle with. I remember that I
>>> had myself once convinced (or was it you?) that the bad case can't
>>> happen, but I was not able to reproduce the argument spontaneously.
>> From my perspective, this one is simply a bug in the static analysis.
>> At line 218, pointer arithmetic was performed on `stack` to get `tsd`.
>> If `stack` were null this would be UB, and if `stack` is not null then
>> you cannot get a null pointer without the arithmetic having invoked
>> UB, so you can conclude that `tsd` is not null.
> I wouldn'd call this a bug. This also assumes that the analyser has do
> "know" from somewhere that `stack` is a pointer that is sufficiently
> far from the 0 address, so the result of the arithmetic can never be a
> 0 valued pointer.
>
> So the problem here is that we use a pointer value that is the result
> of arithmetic to hold the state of a conditional execution.
>
> AFAICS, we could completely avoid that by placing a goto after line
> 220 to jump to line 251. Then the initialization of tsd and the `if
> (!tsd)` conditional (not the code inside) could be omitted.
>
> Jens
>
>


[-- Attachment #2: Type: text/html, Size: 2572 bytes --]

Re: Results of static analysis with clang static analyser

[Jens Gustedt]

[-- Attachment #1: Type: text/plain, Size: 1687 bytes --]

Hello,

Am Freitag, den 25.09.2015, 11:35 -0400 schrieb Matt Avery:
> I'm not sure how keen you are to use asserts, but adding them helps
> the static analyzer not evaluate impossible paths.

I don't think that adding asserts is an option for musl. But for this
case at least which were discussing in particular, this really isn't
needed.

> From the docs:
> ALWAYS analyze a project in its "debug" configuration
> Most projects can be built in a "debug" mode that enables assertions.
> Assertions are picked up by the static analyzer to prune infeasible paths, which
> in some cases can greatly reduce the number of false positives (bogus error
> reports) emitted by the tool.
> 
> Adding an assert(tsd != 0) after the arithmetic operation,

No, here this is really not the right way to do. The test for tsd in
that code is just a check for a particular state of the algorithm,
nothing else. The easiest would really to avoid that completely, for
example the way that I did in the patch that I sent afterwards. There
is exactly one point were that state can be met, and we can just jump
from there. By that we'd avoid a conditional branch all along, making
static analysis even easier :)

> or even better,  assert(stack > __pthread_tsd_size) before should be enough?  

Hm, IIRC stack is a pointer and __pthread_tsd_size is an
integer?

Jens

-- 
:: INRIA Nancy Grand Est ::: Camus ::::::: ICube/ICPS :::
:: ::::::::::::::: office Strasbourg : +33 368854536   ::
:: :::::::::::::::::::::: gsm France : +33 651400183   ::
:: ::::::::::::::: gsm international : +49 15737185122 ::
:: http://icube-icps.unistra.fr/index.php/Jens_Gustedt ::





[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 181 bytes --]

Re: Results of static analysis with clang static analyser

[Szabolcs Nagy]

[-- Attachment #1: Type: text/plain, Size: 367 bytes --]

* Khem Raj <raj.khem@gmail.com> [2015-09-22 22:58:55 -0700]:
> I have run scan-build on musl-git and here are results
> 
> http://busybox.net/~kraj/scan-build-2015-09-22-224330-15962-1/
> 

http://busybox.net/~kraj/scan-build-2015-09-22-224330-15962-1/report-321c4e.html#EndPath

this one is real, status can be REG_ESPACE (meaning oom).

the rest seem ok or benign.

[-- Attachment #2: 0001-regcomp-propagate-allocation-failures.patch --]
[-- Type: text/x-diff, Size: 950 bytes --]

From 321c6a26fade377642664c7a2f6a6f2999266ce1 Mon Sep 17 00:00:00 2001
From: Szabolcs Nagy <nsz@port70.net>
Date: Wed, 23 Sep 2015 18:19:34 +0000
Subject: [PATCH] regcomp: propagate allocation failures

The error code of an allocating function was not checked in tre_add_tag.
---
 src/regex/regcomp.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/src/regex/regcomp.c b/src/regex/regcomp.c
index 978dd87..330de46 100644
--- a/src/regex/regcomp.c
+++ b/src/regex/regcomp.c
@@ -1584,7 +1584,8 @@ tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree,
 		  {
 		    status = tre_add_tag_right(mem, left, tag_left);
 		    tnfa->tag_directions[tag_left] = TRE_TAG_MAXIMIZE;
-		    status = tre_add_tag_right(mem, right, tag_right);
+		    if (status == REG_OK)
+		      status = tre_add_tag_right(mem, right, tag_right);
 		    tnfa->tag_directions[tag_right] = TRE_TAG_MAXIMIZE;
 		  }
 		num_tags += 2;
-- 
2.4.1

Re: Results of static analysis with clang static analyser

[Rich Felker]

On Wed, Sep 23, 2015 at 10:11:32PM +0200, Szabolcs Nagy wrote:
> * Khem Raj <raj.khem@gmail.com> [2015-09-22 22:58:55 -0700]:
> > I have run scan-build on musl-git and here are results
> > 
> > http://busybox.net/~kraj/scan-build-2015-09-22-224330-15962-1/
> > 
> 
> http://busybox.net/~kraj/scan-build-2015-09-22-224330-15962-1/report-321c4e.html#EndPath
> 
> this one is real, status can be REG_ESPACE (meaning oom).
> 
> the rest seem ok or benign.

Committed this and the other (__map_file) one.

Rich

Re: Results of static analysis with clang static analyser

[Szabolcs Nagy]

[-- Attachment #1: Type: text/plain, Size: 311 bytes --]

* Khem Raj <raj.khem@gmail.com> [2015-09-22 22:58:55 -0700]:
> I have run scan-build on musl-git and here are results
> 
> http://busybox.net/~kraj/scan-build-2015-09-22-224330-15962-1/

not a bug, but i'd fix this one:

http://busybox.net/~kraj/scan-build-2015-09-22-224330-15962-1/report-15c463.html#EndPath


[-- Attachment #2: 0001-cosmetic-fix-avoid-reading-uninitialized-memory-in-_.patch --]
[-- Type: text/x-diff, Size: 1166 bytes --]

From da5379205664d62b56acd8f40c405f2b91703afd Mon Sep 17 00:00:00 2001
From: Szabolcs Nagy <nsz@port70.net>
Date: Wed, 23 Sep 2015 20:22:33 +0000
Subject: [PATCH] cosmetic fix: avoid reading uninitialized memory in
 __map_file

The value of *size is not relevant in case of failure, but it's
better not to copy garbage from the stack into it.
(The compiler cannot see through the syscall, so optimization
was not affected by the unspecified value).
---
 src/time/__map_file.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/src/time/__map_file.c b/src/time/__map_file.c
index d06a581..b91eb8e 100644
--- a/src/time/__map_file.c
+++ b/src/time/__map_file.c
@@ -11,9 +11,10 @@ const char unsigned *__map_file(const char *pathname, size_t *size)
 	const unsigned char *map = MAP_FAILED;
 	int fd = __sys_open(pathname, O_RDONLY|O_CLOEXEC|O_NONBLOCK);
 	if (fd < 0) return 0;
-	if (!__syscall(SYS_fstat, fd, &st))
+	if (!__syscall(SYS_fstat, fd, &st)) {
 		map = __mmap(0, st.st_size, PROT_READ, MAP_SHARED, fd, 0);
+		*size = st.st_size;
+	}
 	__syscall(SYS_close, fd);
-	*size = st.st_size;
 	return map == MAP_FAILED ? 0 : map;
 }
-- 
2.4.1