Combination of O3 and UBSan makes seadsa crash on input analysis

[pietroborrello]

It seems a bitcode file compiled with the Undefined Behavior Sanitizer and highest optimization level (-O3) makes seadsa analysis to crash.

Environment

• llvm 10
• sea-dsa: current dev10 branch

To Reproduce

main.cc:

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

// Function extracted from https://github.com/GrokImageCompression/grok/blob/7e232bfecc9efd13c4fc8872cff7cc11c3e72af9/src/lib/jp2/point_transform/mct.cpp#L659
bool decompress_custom(uint8_t* mct_matrix, uint64_t n, uint8_t** pData, uint32_t num_comps,
							uint32_t is_signed)
{
	auto data = (float**)pData;

	(is_signed);

	auto pixel = new float[2 * num_comps];
	auto current_pixel = pixel + num_comps;

	for(uint64_t i = 0; i < n; ++i)
	{
		auto Mct = (float*)mct_matrix;
		for(uint32_t j = 0; j < num_comps; ++j)
		{
			pixel[j] = (float)(*(data[j]));
		}
		for(uint32_t j = 0; j < num_comps; ++j)
		{
			current_pixel[j] = 0;
			for(uint32_t k = 0; k < num_comps; ++k)
				current_pixel[j] += *(Mct++) * pixel[k];
			*(data[j]++) = (float)(current_pixel[j]);
		}
	}
	delete[] pixel;
	return true;
}

int main(int argc) {
	auto data = new uint8_t*[10];
	if (data == nullptr) return 0;
	float *matrix = (float*) malloc(8);
	if (matrix == nullptr) return 0;
	return decompress_custom((uint8_t*)matrix, 3, data , 10, 0);
}

And then to compile and analyze with:

$> clang++ -fsanitize=null -O3 -emit-llvm -c main.cc -o main.bc
$> seadsa -sea-dsa=butd-cs --sea-dsa-aa-eval ./main.bc

seadsa crashes with the following stack trace:

 #0 0x0000000000e1f64f llvm::sys::PrintStackTrace(llvm::raw_ostream&) (../../sea-dsa/build/run/bin/seadsa+0xe1f64f)
 #1 0x0000000000e1d922 llvm::sys::RunSignalHandlers() (../../sea-dsa/build/run/bin/seadsa+0xe1d922)
 #2 0x0000000000e1fb85 SignalHandler(int) (../../sea-dsa/build/run/bin/seadsa+0xe1fb85)
 #3 0x00007f4f0e6cb980 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x12980)
 #4 0x0000000000a95c82 seadsa::Node::isOffsetCollapsed() const [...]sea-dsa/include/seadsa/Graph.hh:682:54
 #5 0x0000000000a95c82 seadsa::Node::addAccessedType(unsigned int, llvm::Type*) [...]sea-dsa/lib/seadsa/Graph.cc:182:9
 #6 0x0000000000aad695 (anonymous namespace)::IntraBlockBuilder::visitLoadInst(llvm::LoadInst&) [...]sea-dsa/lib/seadsa/DsaLocal.cc:701:8
 #7 0x0000000000aad695 llvm::InstVisitor<(anonymous namespace)::IntraBlockBuilder, void>::visitLoad(llvm::LoadInst&) /usr/lib/llvm-10/include/llvm/IR/Instruction.def:172:1
 #8 0x0000000000aad695 llvm::InstVisitor<(anonymous namespace)::IntraBlockBuilder, void>::visit(llvm::Instruction&) /usr/lib/llvm-10/include/llvm/IR/Instruction.def:172:1
 #9 0x0000000000aa89a7 void llvm::InstVisitor<(anonymous namespace)::IntraBlockBuilder, void>::visit<llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::Instruction, false, false, void>, false, false> >(llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::Instruction, false, false, void>, false, false>, llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::Instruction, false, false, void>, false, false>) /usr/lib/llvm-10/include/llvm/IR/InstVisitor.h:0:37
#10 0x0000000000aa89a7 llvm::InstVisitor<(anonymous namespace)::IntraBlockBuilder, void>::visit(llvm::BasicBlock&) /usr/lib/llvm-10/include/llvm/IR/InstVisitor.h:106:5
#11 0x0000000000aa89a7 seadsa::LocalAnalysis::runOnFunction(llvm::Function&, seadsa::Graph&) [...]sea-dsa/lib/seadsa/DsaLocal.cc:1865:18
#12 0x0000000000ac3f8a seadsa::BottomUpAnalysis::runOnModule(llvm::Module&, llvm::DenseMap<llvm::Function const*, std::shared_ptr<seadsa::Graph>, llvm::DenseMapInfo<llvm::Function const*>, llvm::detail::DenseMapPair<llvm::Function const*, std::shared_ptr<seadsa::Graph> > >&) [...]sea-dsa/lib/seadsa/DsaBottomUp.cc:0:0
#13 0x0000000000ab5d8d seadsa::BottomUpTopDownGlobalAnalysis::runOnModule(llvm::Module&) [...]sea-dsa/lib/seadsa/DsaGlobal.cc:651:7
#14 0x0000000000a8f98b std::__uniq_ptr_impl<seadsa::BottomUpTopDownGlobalAnalysis, std::default_delete<seadsa::BottomUpTopDownGlobalAnalysis> >::_M_ptr() const /usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/unique_ptr.h:147:42
#15 0x0000000000a8f98b std::unique_ptr<seadsa::BottomUpTopDownGlobalAnalysis, std::default_delete<seadsa::BottomUpTopDownGlobalAnalysis> >::get() const /usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/unique_ptr.h:332:21
#16 0x0000000000a8f98b std::unique_ptr<seadsa::BottomUpTopDownGlobalAnalysis, std::default_delete<seadsa::BottomUpTopDownGlobalAnalysis> >::operator bool() const /usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/unique_ptr.h:346:16
#17 0x0000000000a8f98b seadsa::SeaDsaAAResult::alias(llvm::MemoryLocation const&, llvm::MemoryLocation const&, llvm::AAQueryInfo&) [...]sea-dsa/lib/seadsa/SeaDsaAliasAnalysis.cc:157:8
#18 0x0000000000453f33 llvm::AAResults::alias(llvm::MemoryLocation const&, llvm::MemoryLocation const&, llvm::AAQueryInfo&) (../../sea-dsa/build/run/bin/seadsa+0x453f33)
#19 0x0000000000466d27 llvm::BasicAAResult::aliasCheck(llvm::Value const*, llvm::LocationSize, llvm::AAMDNodes, llvm::Value const*, llvm::LocationSize, llvm::AAMDNodes, llvm::AAQueryInfo&, llvm::Value const*, llvm::Value const*) (../../sea-dsa/build/run/bin/seadsa+0x466d27)
#20 0x000000000046626b llvm::BasicAAResult::alias(llvm::MemoryLocation const&, llvm::MemoryLocation const&, llvm::AAQueryInfo&) (../../sea-dsa/build/run/bin/seadsa+0x46626b)
#21 0x0000000000453e92 llvm::AAResults::alias(llvm::MemoryLocation const&, llvm::MemoryLocation const&) (../../sea-dsa/build/run/bin/seadsa+0x453e92)
#22 0x000000000045b4f6 llvm::AAEvaluator::runInternal(llvm::Function&, llvm::AAResults&) (../../sea-dsa/build/run/bin/seadsa+0x45b4f6)
#23 0x000000000045ea13 llvm::AAEvalLegacyPass::runOnFunction(llvm::Function&) (../../sea-dsa/build/run/bin/seadsa+0x45ea13)
#24 0x00000000008fd1e6 llvm::FPPassManager::runOnFunction(llvm::Function&) (../../sea-dsa/build/run/bin/seadsa+0x8fd1e6)
#25 0x00000000008fd463 llvm::FPPassManager::runOnModule(llvm::Module&) (../../sea-dsa/build/run/bin/seadsa+0x8fd463)
#26 0x00000000008fd910 llvm::legacy::PassManagerImpl::run(llvm::Module&) (../../sea-dsa/build/run/bin/seadsa+0x8fd910)
#27 0x0000000000450eb5 std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::empty() const /usr/lib/gcc/x86_64-linux-gnu/7.5.0/../../../../include/c++/7.5.0/bits/basic_string.h:1022:29
#28 0x0000000000450eb5 main [...]sea-dsa/tools/seadsa.cc:234:26
#29 0x00007f4f0d0d3bf7 __libc_start_main /build/glibc-S9d2JN/glibc-2.27/csu/../csu/libc-start.c:344:0
#30 0x00000000004502fa _start (../../sea-dsa/build/run/bin/seadsa+0x4502fa)
Stack dump:
0.	Program arguments: ../../sea-dsa/build/run/bin/seadsa -sea-dsa=butd-cs --sea-dsa-aa-eval ./main.bc 
1.	Running pass 'Function Pass Manager' on module './main.bc'.
2.	Running pass 'Exhaustive Alias Analysis Precision Evaluator' on function '@_Z17decompress_customPhmPS_jj'
[1]    16382 segmentation fault  ../../sea-dsa/build/run/bin/seadsa -sea-dsa=butd-cs --sea-dsa-aa-eval 

This is a release version, but the tool would have crashed on:

sea-dsa/lib/seadsa/DsaLocal.cc

Line 699 in 9d8d71a

assert(!base.isNull());

Analysis

It seems that the crash is caused by the tool analysing a load instruction that accesses a %23 = getelementptr inbounds i8*, i8** null, i64 %22 that has a null pointer as base. This instruction is caused by a combination of the NULL checker in UBSan (that checks the Use of a null pointer or creation of a null reference) and the (LoopUnswitch)[https://llvm.org/docs/Passes.html#loop-unswitch-unswitch-loops] pass executed by -O3 that creates the alternative slow path in the loop with the GEP using null. Notice that the program has no path in which pData may be null, but the check is still present due to UBSan.

[pietroborrello]

It seems that the check in DsaLocal at line 667 is specifically made for one or several gep instructions starting from NULL.

sea-dsa/lib/seadsa/DsaLocal.cc

Line 667 in 9d8d71a

if (!m_graph.hasCell(*LI.getPointerOperand()->stripPointerCasts())) {

Here the crash is acually a load of a pointer, which is obtained from a load on a GEP null, so two levels of indirection:

  %arrayidx87.us = getelementptr inbounds i8*, i8** null, i64 %indvars.iv99
  %arrayidx.us = bitcast i8** %arrayidx87.us to float**
  %4 = load float*, float** %arrayidx.us, align 8, !tbaa !4
  %6 = bitcast float* %4 to i32*
  %7 = load i32, i32* %6, align 4, !tbaa !8

It is undefined behavior, but it is present due to UBSan.
I can submit a PR to fix this, but not sure what I should check, instead of simply transforming assert(!base.isNull()); into if(base.isNull()) return; in:

sea-dsa/lib/seadsa/DsaLocal.cc

Line 699 in 9d8d71a

assert(!base.isNull());

Probably the fix should avoid creating the null cell in the first place.

[pietroborrello]

Ok if I enable assertions with PR #131 it actually crashes on

sea-dsa/lib/seadsa/DsaLocal.cc

Line 623 in 9d8d71a

assert(false && "Expression not handled");

after printing as a warning: Unexpected expression at valueCell: %4 = load float*, float** %arrayidx.us, align 8, !tbaa !4 .
This while in visitBitCastInst visiting %6 = bitcast float* %4 to i32* with %4 = load float*, float** %arrayidx.us, align 8, !tbaa !4