bsearch bounds-safe interface does not enforce that size == sizeof(T) (unsound)

[mattmccutchen-cci]

The checked declaration of bsearch is:

checkedc/include/stdlib_checked.h

Lines 90 to 95 in 4e6e0e4

	_Itype_for_any(T) void *bsearch(const void *key : itype(_Ptr<const T>),
	const void *base : itype(_Array_ptr<const T>) byte_count(nmemb * size),
	size_t nmemb, size_t size,
	int ((*compar)(const void *, const void *)) :
	itype(_Ptr<int(_Ptr<const T>, _Ptr<const T>)>)
	) : itype(_Ptr<T>);

The caller is supposed to pass size = sizeof(T), but nothing in the checked declaration expresses this constraint. If the size parameter is too small but nmemb * size is correct, then bsearch may call compar with an argument that points into the middle of a T object, violating type safety, which may lead to a violation of spatial memory safety. (I'd guess that qsort has an analogous problem, but I haven't tested it. Also, memcpy could be abused to overwrite part of a pointer in the destination memory block, leaving an invalid pointer. We should probably review all generic functions in the Checked C headers for problems of this nature.)

For example, the following code compiles with no warnings and generates a segmentation fault at runtime:

#include <stdint.h>
#include <stdlib.h>

#pragma CHECKED_SCOPE on

struct foo {
  _Ptr<int> x;
  uintptr_t y;
};

int my_compar(_Ptr<const struct foo> a, _Ptr<const struct foo> b) {
  return *b->x - *a->x;
}

int main(void) {
  int x1 = 1, x2 = 2;
  struct foo haystack _Checked[1] = {{&x1, 1}};
  struct foo needle = {&x2, 2};
  // OK
  bsearch<struct foo>(&needle, haystack, 1, sizeof(struct foo), my_compar);
  // Segmentation fault
  bsearch<struct foo>(&needle, haystack, 2, sizeof(_Ptr<int>), my_compar);
  return 0;
}

I hoped we might be able to fix this by adding a _Where clause (once _Where clauses are fully implemented in the compiler), something like this:

_Itype_for_any(T) void *bsearch(const void *key : itype(_Ptr<const T>),
                                const void *base : itype(_Array_ptr<const T>) byte_count(nmemb * size),
                                size_t nmemb, size_t size _Where size == sizeof((T)),
                                int ((*compar)(const void *, const void *)) :
                                  itype(_Ptr<int(_Ptr<const T>, _Ptr<const T>)>)
                                ) : itype(_Ptr<T>);

Unfortunately, this declaration generates a compile error about T being an incomplete type and then crashes the parser:

bsearch-proposed.c:5:74: error: invalid application of 'sizeof' to an incomplete type 'T' (aka '(0, 0) __BoundsInterface')
                                size_t nmemb, size_t size _Where size == sizeof((T)),
                                                                         ^      ~~~
clang-11: /home/matt/3c/clang/lib/Parse/ParseExpr.cpp:4137: bool clang::Parser::DeferredParseBoundsAnnotations(std::unique_ptr<llvm::SmallVector<clang::Token, 4> >, clang::BoundsAnnotations&, const clang::Declarator&, clang::Decl*): Assertion `Error' failed.
PLEASE submit a bug report to https://github.com/Microsoft/checkedc-clang/issues and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.	Program arguments: /home/matt/3c/build/bin/clang-11 -cc1 -triple x86_64-unknown-linux-gnu -emit-obj -mrelax-all -disable-free -main-file-name bsearch-proposed.c -mrelocation-model static -mframe-pointer=all -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -fno-split-dwarf-inlining -debugger-tuning=gdb -resource-dir /home/matt/3c/build/lib/clang/11.0.0 -internal-isystem /usr/local/include -internal-isystem /home/matt/3c/build/lib/clang/11.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fdebug-compilation-dir /home/matt/test -ferror-limit 19 -fgnuc-version=4.2.1 -fcolor-diagnostics -faddrsig -o /tmp/bsearch-proposed-f20018.o -x c bsearch-proposed.c 
1.	bsearch-proposed.c:5:84: current parser token ')'
 #0 0x000055fa9691a07b llvm::sys::PrintStackTrace(llvm::raw_ostream&) /home/matt/3c/llvm/lib/Support/Unix/Signals.inc:564:22
 #1 0x000055fa9691a0ee PrintStackTraceSignalHandler(void*) /home/matt/3c/llvm/lib/Support/Unix/Signals.inc:625:1
 #2 0x000055fa96917bda llvm::sys::RunSignalHandlers() /home/matt/3c/llvm/lib/Support/Signals.cpp:68:20
 #3 0x000055fa96917d7b SignalHandler(int) /home/matt/3c/llvm/lib/Support/Unix/Signals.inc:396:31
 #4 0x00007f4c8e6243c0 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x153c0)
 #5 0x00007f4c8e0c418b raise /build/glibc-eX1tMB/glibc-2.31/signal/../sysdeps/unix/sysv/linux/raise.c:51:1
 #6 0x00007f4c8e0a3859 abort /build/glibc-eX1tMB/glibc-2.31/stdlib/abort.c:81:7
 #7 0x00007f4c8e0a3729 get_sysdep_segment_value /build/glibc-eX1tMB/glibc-2.31/intl/loadmsgcat.c:509:8
 #8 0x00007f4c8e0a3729 _nl_load_domain /build/glibc-eX1tMB/glibc-2.31/intl/loadmsgcat.c:970:34
 #9 0x00007f4c8e0b4f36 (/lib/x86_64-linux-gnu/libc.so.6+0x36f36)
#10 0x000055fa98dc62c0 clang::Token::is(clang::tok::TokenKind) const /home/matt/3c/clang/include/clang/Lex/Token.h:97:44
#11 0x000055fa98dc62c0 clang::Token::isOneOf(clang::tok::TokenKind, clang::tok::TokenKind) const /home/matt/3c/clang/include/clang/Lex/Token.h:100:14
#12 0x000055fa98dc62c0 clang::Parser::isTokenParen() const /home/matt/3c/clang/include/clang/Parse/Parser.h:570:23
#13 0x000055fa98dc62c0 clang::Parser::ConsumeParen() /home/matt/3c/clang/include/clang/Parse/Parser.h:614:5
#14 0x000055fa98dc62c0 clang::Parser::ConsumeAnyToken(bool) /home/matt/3c/clang/include/clang/Parse/Parser.h:537:27
#15 0x000055fa98dc62c0 clang::Parser::DeferredParseBoundsAnnotations(std::unique_ptr<llvm::SmallVector<clang::Token, 4u>, std::default_delete<llvm::SmallVector<clang::Token, 4u> > >, clang::BoundsAnnotations&, clang::Declarator const&, clang::Decl*) /home/matt/3c/clang/lib/Parse/ParseExpr.cpp:4139:23
#16 0x000055fa98d8381a clang::Parser::ParseParameterDeclarationClause(clang::DeclaratorContext, clang::ParsedAttributes&, llvm::SmallVectorImpl<clang::DeclaratorChunk::ParamInfo>&, clang::SourceLocation&) /home/matt/3c/clang/lib/Parse/ParseDecl.cpp:7371:48
#17 0x000055fa98d85a03 clang::Parser::ParseFunctionDeclarator(clang::Declarator&, clang::ParsedAttributes&, clang::BalancedDelimiterTracker&, bool, bool) /home/matt/3c/clang/lib/Parse/ParseDecl.cpp:6814:33
#18 0x000055fa98d87a45 clang::Parser::ParseDirectDeclarator(clang::Declarator&) /home/matt/3c/clang/lib/Parse/ParseDecl.cpp:6476:7
#19 0x000055fa98d71538 clang::Parser::ParseDeclaratorInternal(clang::Declarator&, void (clang::Parser::*)(clang::Declarator&)) (.localalias) /home/matt/3c/clang/lib/Parse/ParseDecl.cpp:6118:1
#20 0x000055fa98d71980 clang::Parser::ParseDeclaratorInternal(clang::Declarator&, void (clang::Parser::*)(clang::Declarator&)) (.localalias) /home/matt/3c/clang/lib/Parse/ParseDecl.cpp:6050:5
#21 0x000055fa98d71e3b clang::Parser::ParseDeclarator(clang::Declarator&) /home/matt/3c/clang/lib/Parse/ParseDecl.cpp:5894:1
#22 0x000055fa98d7eff5 clang::Declarator::hasName() const /home/matt/3c/clang/include/clang/Sema/DeclSpec.h:2287:28
#23 0x000055fa98d7eff5 clang::Parser::ParseDeclGroup(clang::ParsingDeclSpec&, clang::DeclaratorContext, clang::SourceLocation*, clang::Parser::ForRangeInit*) /home/matt/3c/clang/lib/Parse/ParseDecl.cpp:1919:17
#24 0x000055fa98d5c4e8 clang::Sema::CheckedScopeRAII::~CheckedScopeRAII() /home/matt/3c/clang/include/clang/Sema/Sema.h:4427:28
#25 0x000055fa98d5c4e8 clang::Parser::ParseDeclOrFunctionDefInternal(clang::Parser::ParsedAttributesWithRange&, clang::ParsingDeclSpec&, clang::AccessSpecifier) /home/matt/3c/clang/lib/Parse/Parser.cpp:1042:57
#26 0x000055fa98d5cabc clang::Parser::ParseDeclarationOrFunctionDefinition(clang::Parser::ParsedAttributesWithRange&, clang::ParsingDeclSpec*, clang::AccessSpecifier) /home/matt/3c/clang/lib/Parse/Parser.cpp:1154:57
#27 0x000055fa98d5d772 clang::Parser::ParseExternalDeclaration(clang::Parser::ParsedAttributesWithRange&, clang::ParsingDeclSpec*) (.localalias) /home/matt/3c/clang/lib/Parse/Parser.cpp:956:58
#28 0x000055fa98d5da75 clang::Parser::ParseTopLevelDecl(clang::OpaquePtr<clang::DeclGroupRef>&, bool) /home/matt/3c/clang/lib/Parse/Parser.cpp:704:42
#29 0x000055fa98d538cf clang::ParseAST(clang::Sema&, bool, bool) /home/matt/3c/clang/lib/Parse/ParseAST.cpp:157:56
#30 0x000055fa976dd137 clang::ASTFrontendAction::ExecuteAction() /home/matt/3c/clang/lib/Frontend/FrontendAction.cpp:1059:1
#31 0x000055fa977e77ca clang::CodeGenAction::ExecuteAction() /home/matt/3c/clang/lib/CodeGen/CodeGenAction.cpp:1185:1
#32 0x000055fa976dfadc clang::FrontendAction::Execute() /home/matt/3c/clang/lib/Frontend/FrontendAction.cpp:950:21
#33 0x000055fa9761fd1f llvm::Error::setChecked(bool) /home/matt/3c/llvm/include/llvm/Support/Error.h:305:22
#34 0x000055fa9761fd1f llvm::Error::operator bool() /home/matt/3c/llvm/include/llvm/Support/Error.h:236:15
#35 0x000055fa9761fd1f clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) /home/matt/3c/clang/lib/Frontend/CompilerInstance.cpp:984:42
#36 0x000055fa977dcf20 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) /home/matt/3c/clang/lib/FrontendTool/ExecuteCompilerInvocation.cpp:278:38
#37 0x000055fa95194ef8 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) /home/matt/3c/clang/tools/driver/cc1_main.cpp:240:40
#38 0x000055fa9518ef55 ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) /home/matt/3c/clang/tools/driver/driver.cpp:330:20
#39 0x000055fa95191a39 main /home/matt/3c/clang/tools/driver/driver.cpp:407:26
#40 0x00007f4c8e0a50b3 __libc_start_main /build/glibc-eX1tMB/glibc-2.31/csu/../csu/libc-start.c:342:3
#41 0x000055fa9518e9ce _start (/home/matt/3c/build/bin/clang-11+0x2ada9ce)

Once the parser crash is fixed, I guess the compiler would need to be enhanced to allow sizeof(T) in a _Where clause and instantiate T at each call site.