[RFC] -fsanitize=pointer-overflow support (PR sanitizer/80998)

Hi!

The following patch adds -fsanitize=pointer-overflow support,
which adds instrumentation (included in -fsanitize=undefined) that checks
that pointer arithmetics doesn't wrap.  If the offset on ptr p+ off when treating
it as signed value is non-negative, we check whether the result is bigger
(uintptr_t comparison) than ptr, if it is negative in ssizetype, we check
whether the result is smaller than ptr, otherwise we check at runtime
whether (ssizetype) off < 0 and do the check based on that.
The patch checks both POINTER_PLUS_EXPR, as well as e.g. ADDR_EXPR of
handled components, and even handled components themselves (exception
is for constant offset when the base is an automatic non-VLA decl or
decl that binds to current function where we can at compile time for
sure guarantee it will fit).

Martin has said he'll write the sanopt part of optimization
(if UBSAN_PTR for some pointer is dominated by UBSAN_PTR for the same
pointer and the offset is constant in both cases and equal or absolute value
bigger and same sign in the dominating UBSAN_PTR, we can avoid the dominated
check).  

For the cases where there is a dereference (i.e. not ADDR_EXPR of the
handled component or POINTER_PLUS_EXPR), I wonder if we couldn't ignore
say constant offsets in range <-4096, 4096> or something similar, hoping
people don't have anything mapped at the page 0 and -pagesize in hosted
env.  Thoughts on that?

I've bootstrapped/regtested the patch on x86_64-linux and i686-linux
and additionally bootstrapped/regtested with bootstrap-ubsan on both too.
The latter revealed a couple of issues I'd like to discuss:

1) libcpp/symtab.c contains a couple of spots reduced into:
#define DELETED ((char *) -1)
void bar (char *);
void
foo (char *p)
{
  if (p && p != DELETED)
    bar (p);
}
where we fold it early into if ((p p+ -1) <= (char *) -3)
and as the instrumentation is done during ubsan pass, if p is NULL,
we diagnose this as invalid pointer overflow from NULL to 0xffff*f.
Shall we change the folder so that during GENERIC folding it
actually does the addition and comparison in pointer_sized_int
instead (my preference), or shall I move the UBSAN_PTR instrumentation
earlier into the FEs (but then I still risk stuff is folded earlier)?

2) libcpp/line-map.c has this:
static int
location_adhoc_data_update (void **slot, void *data)
{
  *((char **) slot) += *((int64_t *) data);
  return 1;
}
where the (why int64_t always?, we really need just intptr_t) adjusts
one pointer from an unrelated one (result of realloc).  That is a UB
and actually can trigger this sanitization if the two regions are
far away from each other, e.g. on i686-linux:
../../libcpp/line-map.c:102:21: runtime error: pointer index expression with base 0x0899e308 overflowed to 0xf74c4ab8
../../libcpp/line-map.c:102:21: runtime error: pointer index expression with base 0x08add7c0 overflowed to 0xf74c9a08
../../libcpp/line-map.c:102:21: runtime error: pointer index expression with base 0x092ba308 overflowed to 0xf741cab8
../../libcpp/line-map.c:102:21: runtime error: pointer index expression with base 0x0a3757c0 overflowed to 0xf7453a08
Shall we perform the addition in uintptr_t instead to make it
implementation defined rather than UB?

3) not really related to this patch, but something I also saw during the
bootstrap-ubsan on i686-linux:
../../gcc/bitmap.c:141:12: runtime error: signed integer overflow: -2147426384 - 2147475412 cannot be represented in type 'int'
../../gcc/bitmap.c:141:12: runtime error: signed integer overflow: -2147426384 - 2147478324 cannot be represented in type 'int'
../../gcc/bitmap.c:141:12: runtime error: signed integer overflow: -2147450216 - 2147451580 cannot be represented in type 'int'
../../gcc/bitmap.c:141:12: runtime error: signed integer overflow: -2147450216 - 2147465664 cannot be represented in type 'int'
../../gcc/bitmap.c:141:12: runtime error: signed integer overflow: -2147469348 - 2147451544 cannot be represented in type 'int'
../../gcc/bitmap.c:141:12: runtime error: signed integer overflow: -2147482364 - 2147475376 cannot be represented in type 'int'
../../gcc/bitmap.c:141:12: runtime error: signed integer overflow: -2147483624 - 2147475376 cannot be represented in type 'int'
../../gcc/bitmap.c:141:12: runtime error: signed integer overflow: -2147483628 - 2147451544 cannot be represented in type 'int'
../../gcc/memory-block.cc:59:4: runtime error: signed integer overflow: -2147426384 - 2147475376 cannot be represented in type 'int'
../../gcc/memory-block.cc:59:4: runtime error: signed integer overflow: -2147450216 - 2147451544 cannot be represented in type 'int'
The problem here is that we lower pointer subtraction, e.g.
long foo (char *p, char *q) { return q - p; }
as return (ptrdiff_t) ((ssizetype) q - (ssizetype) p);
and even for a valid testcase where we have an array across
the middle of the virtual address space, say the first one above
is (char *) 0x8000dfb0 - (char *) 0x7fffdfd4 subtraction, even if
there is 128KB array starting at 0x7fffd000, it will yield
UB (not in the source, but in whatever the compiler lowered it into).
So, shall we instead do the subtraction in sizetype and only then
cast?  For sizeof (*ptr) > 1 I think we have some outstanding PR,
and it is more difficult to find out in what types to compute it.
Or do we want to introduce POINTER_DIFF_EXPR?

2017-06-19  Jakub Jelinek  <jakub@redhat.com>

	PR sanitizer/80998
	* sanopt.c (pass_sanopt::execute): Handle IFN_UBSAN_PTR.
	* tree-ssa-alias.c (call_may_clobber_ref_p_1): Likewise.
	* flag-types.h (enum sanitize_code): Add SANITIZER_POINTER_OVERFLOW.
	Or it into SANITIZER_UNDEFINED.
	* ubsan.c: Include gimple-fold.h and varasm.h.
	(ubsan_expand_null_ifn): Use PROB_VERY_LIKELY instead of
	REG_BR_PROB_BASE - PROB_VERY_UNLIKELY.
	(ubsan_expand_ptr_ifn): New function.
	(instrument_pointer_overflow): New function.
	(maybe_instrument_pointer_overflow): New function.
	(instrument_object_size): Formatting fix.
	(pass_ubsan::execute): Call instrument_pointer_overflow
	and maybe_instrument_pointer_overflow.
	* internal-fn.c (expand_UBSAN_PTR): New function.
	* ubsan.h (ubsan_expand_ptr_ifn): Declare.
	* sanitizer.def (__ubsan_handle_pointer_overflow,
	__ubsan_handle_pointer_overflow_abort): New builtins.
	* tree-ssa-tail-merge.c (merge_stmts_p): Handle IFN_UBSAN_PTR.
	* internal-fn.def (UBSAN_PTR): New internal function.
	* opts.c (sanitizer_opts): Add pointer-overflow.
	* lto-streamer-in.c (input_function): Handle IFN_UBSAN_PTR.
gcc/testsuite/
	* c-c++-common/ubsan/ptr-overflow-1.c: New test.
	* c-c++-common/ubsan/ptr-overflow-2.c: New test.
libsanitizer/
	* ubsan/ubsan_handlers.cc: Cherry-pick upstream r304461.
	* ubsan/ubsan_checks.inc: Likewise.
	* ubsan/ubsan_handlers.h: Likewise.

	Jakub

[RFC] -fsanitize=pointer-overflow support (PR sanitizer/80998)

Commit Message

Comments

Patch