[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

steakhal wrote:

FYI this PR likely caused a crash, reported in #47.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[LLVM Continuous Integration via cfe-commits]

llvm-ci wrote:

LLVM Buildbot has detected a new failure on builder 
`openmp-offload-libc-amdgpu-runtime` running on `omp-vega20-1` while building 
`clang` at step 10 "Add check check-offload".

Full details are available at: 
https://lab.llvm.org/buildbot/#/builders/73/builds/6544


Here is the relevant piece of the build log for the reference

```
Step 10 (Add check check-offload) failure: test (failure)
 TEST 'libomptarget :: amdgcn-amd-amdhsa :: 
offloading/parallel_target_teams_reduction.cpp' FAILED 
Exit Code: 2

Command Output (stdout):
--
# RUN: at line 1
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/./bin/clang++
 -fopenmp-I 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.src/offload/test 
-I 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/openmp/runtime/src
 -L 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/offload
 -L /home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/./lib -L 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/openmp/runtime/src
  -nogpulib 
-Wl,-rpath,/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/offload
 
-Wl,-rpath,/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/openmp/runtime/src
 
-Wl,-rpath,/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/./lib
  -fopenmp-targets=amdgcn-amd-amdhsa 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.src/offload/test/offloading/parallel_target_teams_reduction.cpp
 -o 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/offload/test/amdgcn-amd-amdhsa/offloading/Output/parallel_target_teams_reduction.cpp.tmp
 -Xoffload-linker -lc -Xoffload-linker -lm 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/./lib/libomptarget.devicertl.a
 && 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/offload/test/amdgcn-amd-amdhsa/offloading/Output/parallel_target_teams_reduction.cpp.tmp
 | 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/./bin/FileCheck
 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.src/offload/test/offloading/parallel_target_teams_reduction.cpp
# executed command: 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/./bin/clang++
 -fopenmp -I 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.src/offload/test 
-I 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/openmp/runtime/src
 -L 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/offload
 -L /home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/./lib -L 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/openmp/runtime/src
 -nogpulib 
-Wl,-rpath,/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/offload
 
-Wl,-rpath,/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/openmp/runtime/src
 
-Wl,-rpath,/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/./lib
 -fopenmp-targets=amdgcn-amd-amdhsa 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.src/offload/test/offloading/parallel_target_teams_reduction.cpp
 -o 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/offload/test/amdgcn-amd-amdhsa/offloading/Output/parallel_target_teams_reduction.cpp.tmp
 -Xoffload-linker -lc -Xoffload-linker -lm 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/./lib/libomptarget.devicertl.a
# executed command: 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/offload/test/amdgcn-amd-amdhsa/offloading/Output/parallel_target_teams_reduction.cpp.tmp
# executed command: 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/./bin/FileCheck
 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.src/offload/test/offloading/parallel_target_teams_reduction.cpp
# RUN: at line 2
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/./bin/clang++
 -fopenmp-I 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.src/offload/test 
-I 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/openmp/runtime/src
 -L 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/offload
 -L /home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/./lib -L 
/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/openmp/runtime/src
  -nogpulib 
-Wl,-rpath,/home/ompworker/bbot/openmp-offload-libc-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/offload
 
-Wl,-rpath,/hom

[clang] [analyzer] Model overflow builtins (PR #102602)

[LLVM Continuous Integration via cfe-commits]

llvm-ci wrote:

LLVM Buildbot has detected a new failure on builder `lldb-arm-ubuntu` running 
on `linaro-lldb-arm-ubuntu` while building `clang` at step 6 "test".

Full details are available at: 
https://lab.llvm.org/buildbot/#/builders/18/builds/4864


Here is the relevant piece of the build log for the reference

```
Step 6 (test) failure: build (failure)
...
PASS: lldb-api :: lang/cpp/incomplete-types/TestCppIncompleteTypes.py (794 of 
2814)
PASS: lldb-api :: 
lang/cpp/incomplete-types/members/TestCppIncompleteTypeMembers.py (795 of 2814)
PASS: lldb-api :: lang/cpp/keywords_enabled/TestCppKeywordsEnabled.py (796 of 
2814)
PASS: lldb-api :: lang/cpp/inlines/TestInlines.py (797 of 2814)
PASS: lldb-api :: lang/cpp/lambdas/TestLambdas.py (798 of 2814)
PASS: lldb-api :: lang/cpp/llvm-style/TestLLVMStyle.py (799 of 2814)
PASS: lldb-api :: lang/cpp/limit-debug-info/TestWithLimitDebugInfo.py (800 of 
2814)
UNSUPPORTED: lldb-api :: lang/cpp/modules-import/TestCXXModulesImport.py (801 
of 2814)
PASS: lldb-api :: lang/cpp/multiple-inheritance/TestCppMultipleInheritance.py 
(802 of 2814)
PASS: lldb-api :: 
lang/cpp/member-and-local-vars-with-same-name/TestMembersAndLocalsWithSameName.py
 (803 of 2814)
FAIL: lldb-api :: 
lang/c/shared_lib_stripped_symbols/TestSharedLibStrippedSymbols.py (804 of 2814)
 TEST 'lldb-api :: 
lang/c/shared_lib_stripped_symbols/TestSharedLibStrippedSymbols.py' FAILED 

Script:
--
/usr/bin/python3.10 
/home/tcwg-buildbot/worker/lldb-arm-ubuntu/llvm-project/lldb/test/API/dotest.py 
-u CXXFLAGS -u CFLAGS --env ARCHIVER=/usr/local/bin/llvm-ar --env 
OBJCOPY=/usr/bin/llvm-objcopy --env 
LLVM_LIBS_DIR=/home/tcwg-buildbot/worker/lldb-arm-ubuntu/build/./lib --env 
LLVM_INCLUDE_DIR=/home/tcwg-buildbot/worker/lldb-arm-ubuntu/build/include --env 
LLVM_TOOLS_DIR=/home/tcwg-buildbot/worker/lldb-arm-ubuntu/build/./bin --arch 
armv8l --build-dir 
/home/tcwg-buildbot/worker/lldb-arm-ubuntu/build/lldb-test-build.noindex 
--lldb-module-cache-dir 
/home/tcwg-buildbot/worker/lldb-arm-ubuntu/build/lldb-test-build.noindex/module-cache-lldb/lldb-api
 --clang-module-cache-dir 
/home/tcwg-buildbot/worker/lldb-arm-ubuntu/build/lldb-test-build.noindex/module-cache-clang/lldb-api
 --executable /home/tcwg-buildbot/worker/lldb-arm-ubuntu/build/./bin/lldb 
--compiler /home/tcwg-buildbot/worker/lldb-arm-ubuntu/build/./bin/clang 
--dsymutil /home/tcwg-buildbot/worker/lldb-arm-ubuntu/build/./bin/dsymutil 
--llvm-tools-dir /home/tcwg-buildbot/worker/lldb-arm-ubuntu/build/./bin 
--lldb-obj-root /home/tcwg-buildbot/worker/lldb-arm-ubuntu/build/tools/lldb 
--lldb-libs-dir /home/tcwg-buildbot/worker/lldb-arm-ubuntu/build/./lib 
/home/tcwg-buildbot/worker/lldb-arm-ubuntu/llvm-project/lldb/test/API/lang/c/shared_lib_stripped_symbols
 -p TestSharedLibStrippedSymbols.py
--
Exit Code: 1

Command Output (stdout):
--
lldb version 20.0.0git (https://github.com/llvm/llvm-project.git revision 
a017ed04cc9bcc75b3c3ef35c923dbe7dc4606f8)
  clang revision a017ed04cc9bcc75b3c3ef35c923dbe7dc4606f8
  llvm revision a017ed04cc9bcc75b3c3ef35c923dbe7dc4606f8
Skipping the following test categories: ['libc++', 'dsym', 'gmodules', 
'debugserver', 'objc']

--
Command Output (stderr):
--
UNSUPPORTED: LLDB 
(/home/tcwg-buildbot/worker/lldb-arm-ubuntu/build/bin/clang-arm) :: 
test_expr_dsym (TestSharedLibStrippedSymbols.SharedLibStrippedTestCase) (test 
case does not fall in any category of interest for this run) 
PASS: LLDB (/home/tcwg-buildbot/worker/lldb-arm-ubuntu/build/bin/clang-arm) :: 
test_expr_dwarf (TestSharedLibStrippedSymbols.SharedLibStrippedTestCase)
FAIL: LLDB (/home/tcwg-buildbot/worker/lldb-arm-ubuntu/build/bin/clang-arm) :: 
test_expr_dwo (TestSharedLibStrippedSymbols.SharedLibStrippedTestCase)
UNSUPPORTED: LLDB 
(/home/tcwg-buildbot/worker/lldb-arm-ubuntu/build/bin/clang-arm) :: 
test_frame_variable_dsym 
(TestSharedLibStrippedSymbols.SharedLibStrippedTestCase) (test case does not 
fall in any category of interest for this run) 
XFAIL: LLDB (/home/tcwg-buildbot/worker/lldb-arm-ubuntu/build/bin/clang-arm) :: 
test_frame_variable_dwarf 
(TestSharedLibStrippedSymbols.SharedLibStrippedTestCase)
XFAIL: LLDB (/home/tcwg-buildbot/worker/lldb-arm-ubuntu/build/bin/clang-arm) :: 
test_frame_variable_dwo (TestSharedLibStrippedSymbols.SharedLibStrippedTestCase)
==
FAIL: test_expr_dwo (TestSharedLibStrippedSymbols.SharedLibStrippedTestCase)
   Test that types work when defined in a shared library and forwa/d-declared 
in the main executable
--
Traceback (most recent call last):
  File 
"/home/tcwg-buildbot/worker/lldb-arm-ubuntu/llvm-project/lldb/packages/Python/lldbsuite/test/lldbtest.py",
 line 1769, in test_method
return attrvalue(self)
  File 
"/home/tcwg-buildbot/worker/lldb-arm-ubuntu/llvm-project/lldb/test/API/lang/c/shared_lib_stripped_symbols/TestSharedLibStripp

[clang] [analyzer] Model overflow builtins (PR #102602)

[LLVM Continuous Integration via cfe-commits]

llvm-ci wrote:

LLVM Buildbot has detected a new failure on builder `fuchsia-x86_64-linux` 
running on `fuchsia-debian-64-us-central1-a-1` while building `clang` at step 4 
"annotate".

Full details are available at: 
https://lab.llvm.org/buildbot/#/builders/11/builds/6049


Here is the relevant piece of the build log for the reference

```
Step 4 (annotate) failure: 'python 
../llvm-zorg/zorg/buildbot/builders/annotated/fuchsia-linux.py ...' (failure)
...
[666/1327] Building CXX object 
unittests/ADT/CMakeFiles/ADTTests.dir/EnumeratedArrayTest.cpp.o
clang++: warning: optimization flag '-ffat-lto-objects' is not supported 
[-Wignored-optimization-argument]
[667/1327] Linking CXX executable bin/yaml2obj
[667/1327] Running lld test suite
llvm-lit: 
/var/lib/buildbot/fuchsia-x86_64-linux/llvm-project/llvm/utils/lit/lit/llvm/config.py:506:
 note: using ld.lld: 
/var/lib/buildbot/fuchsia-x86_64-linux/build/llvm-build-8ttjmpeb/bin/ld.lld
llvm-lit: 
/var/lib/buildbot/fuchsia-x86_64-linux/llvm-project/llvm/utils/lit/lit/llvm/config.py:506:
 note: using lld-link: 
/var/lib/buildbot/fuchsia-x86_64-linux/build/llvm-build-8ttjmpeb/bin/lld-link
llvm-lit: 
/var/lib/buildbot/fuchsia-x86_64-linux/llvm-project/llvm/utils/lit/lit/llvm/config.py:506:
 note: using ld64.lld: 
/var/lib/buildbot/fuchsia-x86_64-linux/build/llvm-build-8ttjmpeb/bin/ld64.lld
llvm-lit: 
/var/lib/buildbot/fuchsia-x86_64-linux/llvm-project/llvm/utils/lit/lit/llvm/config.py:506:
 note: using wasm-ld: 
/var/lib/buildbot/fuchsia-x86_64-linux/build/llvm-build-8ttjmpeb/bin/wasm-ld
-- Testing: 2990 tests, 60 workers --
Testing:  0.. 10.. 20
FAIL: lld :: ELF/basic-block-sections-pc32reloc.s (702 of 2990)
 TEST 'lld :: ELF/basic-block-sections-pc32reloc.s' FAILED 

Exit Code: 1

Command Output (stderr):
--
RUN: at line 7: 
/var/lib/buildbot/fuchsia-x86_64-linux/build/llvm-build-8ttjmpeb/bin/llvm-mc 
-filetype=obj -triple=x86_64 
/var/lib/buildbot/fuchsia-x86_64-linux/llvm-project/lld/test/ELF/basic-block-sections-pc32reloc.s
 -o 
/var/lib/buildbot/fuchsia-x86_64-linux/build/llvm-build-8ttjmpeb/tools/lld/test/ELF/Output/basic-block-sections-pc32reloc.s.tmp.o
+ /var/lib/buildbot/fuchsia-x86_64-linux/build/llvm-build-8ttjmpeb/bin/llvm-mc 
-filetype=obj -triple=x86_64 
/var/lib/buildbot/fuchsia-x86_64-linux/llvm-project/lld/test/ELF/basic-block-sections-pc32reloc.s
 -o 
/var/lib/buildbot/fuchsia-x86_64-linux/build/llvm-build-8ttjmpeb/tools/lld/test/ELF/Output/basic-block-sections-pc32reloc.s.tmp.o
RUN: at line 8: 
/var/lib/buildbot/fuchsia-x86_64-linux/build/llvm-build-8ttjmpeb/bin/llvm-objdump
 -dr 
/var/lib/buildbot/fuchsia-x86_64-linux/build/llvm-build-8ttjmpeb/tools/lld/test/ELF/Output/basic-block-sections-pc32reloc.s.tmp.o|
 /var/lib/buildbot/fuchsia-x86_64-linux/build/llvm-build-8ttjmpeb/bin/FileCheck 
/var/lib/buildbot/fuchsia-x86_64-linux/llvm-project/lld/test/ELF/basic-block-sections-pc32reloc.s
 --check-prefix=RELOC
+ 
/var/lib/buildbot/fuchsia-x86_64-linux/build/llvm-build-8ttjmpeb/bin/llvm-objdump
 -dr 
/var/lib/buildbot/fuchsia-x86_64-linux/build/llvm-build-8ttjmpeb/tools/lld/test/ELF/Output/basic-block-sections-pc32reloc.s.tmp.o
+ 
/var/lib/buildbot/fuchsia-x86_64-linux/build/llvm-build-8ttjmpeb/bin/FileCheck 
/var/lib/buildbot/fuchsia-x86_64-linux/llvm-project/lld/test/ELF/basic-block-sections-pc32reloc.s
 --check-prefix=RELOC
/var/lib/buildbot/fuchsia-x86_64-linux/llvm-project/lld/test/ELF/basic-block-sections-pc32reloc.s:13:15:
 error: RELOC-NEXT: is not on the line after the previous match
# RELOC-NEXT: R_X86_64_PC32
  ^
:11:20: note: 'next' match was here
 000a: R_X86_64_PC32 .text-0x1
   ^
:2:63: note: previous match ended here
/var/lib/buildbot/fuchsia-x86_64-linux/build/llvm-build-8ttjmpeb/tools/lld/test/ELF/Output/basic-block-sections-pc32reloc.s.tmp.o:
 file format elf64-x86-64
  ^
:3:1: note: non-matching line after previous match is here

^

Input file: 
Check file: 
/var/lib/buildbot/fuchsia-x86_64-linux/llvm-project/lld/test/ELF/basic-block-sections-pc32reloc.s

-dump-input=help explains the following input dump.

Input was:
<<
 .
 .
 .
 6:  : 
 7:  0: 0f 1f 00 nopl (%rax) 
 8:  3: 0f 84 00 00 00 00 je 0x9  
 9:  0005: R_X86_64_PLT32 .text-0x4 
10:  9: e9 00 00 00 00 jmp 0xe  
Step 7 (check) failure: check (failure)
...
[666/1327] Building CXX object 
unittests/ADT/CMakeFiles/ADTTests.dir/EnumeratedArrayTest.cpp.o
clang++: warning: optimization flag '-ffat-lto-objects' is not supported 
[-Wignored-optimization-argument]
[667/1327] Linking CXX executable bin/yaml2obj
[667/1327] Running lld test suite
llvm-lit: 
/var/lib/buildbot/fuchsia-x86_64-linux/llvm-project/llvm/utils/lit/lit/llvm/config.py:506:
 note: using ld.lld: 
/var/lib/buildbot/fuchsia-x86_64-linux/build/llvm-build-8ttjmpeb/bin/ld.lld
llvm-lit

[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

https://github.com/steakhal closed 
https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

https://github.com/pskrgag updated 
https://github.com/llvm/llvm-project/pull/102602

>From 7b4f999b39f4308cab253204e6be41ea7a70f695 Mon Sep 17 00:00:00 2001
From: Pavel Skripkin 
Date: Fri, 9 Aug 2024 14:37:47 +0300
Subject: [PATCH 01/12] clang/csa: add initial support for builtin overflow

---
 .../Checkers/BuiltinFunctionChecker.cpp   | 124 +-
 clang/test/Analysis/builtin_overflow.c|  65 +
 .../test/Analysis/out-of-bounds-diagnostics.c |  17 +++
 3 files changed, 204 insertions(+), 2 deletions(-)
 create mode 100644 clang/test/Analysis/builtin_overflow.c

diff --git a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp 
b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
index b198b1c2ff4d11..0c8b9fa3d947b0 100644
--- a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
+++ b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
@@ -21,16 +21,67 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 
+QualType getOverflowBuiltinResultType(const CallEvent &Call) {
+  assert(Call.getNumArgs() == 3);
+
+  return Call.getArgExpr(2)->getType()->getPointeeType();
+}
+
+QualType getOverflowBuiltinResultType(const CallEvent &Call, CheckerContext &C,
+  unsigned BI) {
+  assert(Call.getNumArgs() == 3);
+
+  ASTContext &Ast = C.getASTContext();
+
+  switch (BI) {
+  case Builtin::BI__builtin_smul_overflow:
+  case Builtin::BI__builtin_ssub_overflow:
+  case Builtin::BI__builtin_sadd_overflow:
+return Ast.IntTy;
+  case Builtin::BI__builtin_smull_overflow:
+  case Builtin::BI__builtin_ssubl_overflow:
+  case Builtin::BI__builtin_saddl_overflow:
+return Ast.LongTy;
+  case Builtin::BI__builtin_smulll_overflow:
+  case Builtin::BI__builtin_ssubll_overflow:
+  case Builtin::BI__builtin_saddll_overflow:
+return Ast.LongLongTy;
+  case Builtin::BI__builtin_umul_overflow:
+  case Builtin::BI__builtin_usub_overflow:
+  case Builtin::BI__builtin_uadd_overflow:
+return Ast.UnsignedIntTy;
+  case Builtin::BI__builtin_umull_overflow:
+  case Builtin::BI__builtin_usubl_overflow:
+  case Builtin::BI__builtin_uaddl_overflow:
+return Ast.UnsignedLongTy;
+  case Builtin::BI__builtin_umulll_overflow:
+  case Builtin::BI__builtin_usubll_overflow:
+  case Builtin::BI__builtin_uaddll_overflow:
+return Ast.UnsignedLongLongTy;
+  case Builtin::BI__builtin_mul_overflow:
+  case Builtin::BI__builtin_sub_overflow:
+  case Builtin::BI__builtin_add_overflow:
+return getOverflowBuiltinResultType(Call);
+  default:
+assert(false && "Unknown overflow builtin");
+  }
+}
+
 class BuiltinFunctionChecker : public Checker {
 public:
   bool evalCall(const CallEvent &Call, CheckerContext &C) const;
+  void HandleOverflowBuiltin(const CallEvent &Call, CheckerContext &C,
+ BinaryOperator::Opcode Op,
+ QualType ResultType) const;
 
 private:
   // From: clang/include/clang/Basic/Builtins.def
@@ -50,6 +101,44 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+void BuiltinFunctionChecker::HandleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // All __builtin_*_overflow functions take 3 argumets.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  // TODO: Handle overflows with values that known to overflow. Like INT_MAX + 
1
+  // should not produce state for non-overflow case and threat it as
+  // unreachable.
+
+  // Handle non-overflow case.
+  {
+ProgramStateRef StateSuccess =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs())
+  StateSuccess = StateSuccess->bindLoc(*L, RetVal, C.getLocationContext());
+
+C.addTransition(StateSuccess);
+  }
+
+  // Handle overflow case.
+  {
+C.addTransition(
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(true)));
+  }
+}
+
 bool BuiltinFunctionChecker::isBuiltinLikeFunction(
 const CallEvent &Call) const {
   const auto *FD = llvm::dyn_cast_or_null(Call.getDecl());
@@ -82,10 +171,41 @@ bool BuiltinFunctionC

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

pskrgag wrote:

Ah, this dangling reference to rvalue... I do remember why I bind `get{Min, 
Max}Value` to locals -- `ConcreteInt` takes a reference to `APSInt`, so it's 
not possible to pass result of these calls directly to constructor.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

https://github.com/pskrgag updated 
https://github.com/llvm/llvm-project/pull/102602

>From 7b4f999b39f4308cab253204e6be41ea7a70f695 Mon Sep 17 00:00:00 2001
From: Pavel Skripkin 
Date: Fri, 9 Aug 2024 14:37:47 +0300
Subject: [PATCH 01/11] clang/csa: add initial support for builtin overflow

---
 .../Checkers/BuiltinFunctionChecker.cpp   | 124 +-
 clang/test/Analysis/builtin_overflow.c|  65 +
 .../test/Analysis/out-of-bounds-diagnostics.c |  17 +++
 3 files changed, 204 insertions(+), 2 deletions(-)
 create mode 100644 clang/test/Analysis/builtin_overflow.c

diff --git a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp 
b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
index b198b1c2ff4d11..0c8b9fa3d947b0 100644
--- a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
+++ b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
@@ -21,16 +21,67 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 
+QualType getOverflowBuiltinResultType(const CallEvent &Call) {
+  assert(Call.getNumArgs() == 3);
+
+  return Call.getArgExpr(2)->getType()->getPointeeType();
+}
+
+QualType getOverflowBuiltinResultType(const CallEvent &Call, CheckerContext &C,
+  unsigned BI) {
+  assert(Call.getNumArgs() == 3);
+
+  ASTContext &Ast = C.getASTContext();
+
+  switch (BI) {
+  case Builtin::BI__builtin_smul_overflow:
+  case Builtin::BI__builtin_ssub_overflow:
+  case Builtin::BI__builtin_sadd_overflow:
+return Ast.IntTy;
+  case Builtin::BI__builtin_smull_overflow:
+  case Builtin::BI__builtin_ssubl_overflow:
+  case Builtin::BI__builtin_saddl_overflow:
+return Ast.LongTy;
+  case Builtin::BI__builtin_smulll_overflow:
+  case Builtin::BI__builtin_ssubll_overflow:
+  case Builtin::BI__builtin_saddll_overflow:
+return Ast.LongLongTy;
+  case Builtin::BI__builtin_umul_overflow:
+  case Builtin::BI__builtin_usub_overflow:
+  case Builtin::BI__builtin_uadd_overflow:
+return Ast.UnsignedIntTy;
+  case Builtin::BI__builtin_umull_overflow:
+  case Builtin::BI__builtin_usubl_overflow:
+  case Builtin::BI__builtin_uaddl_overflow:
+return Ast.UnsignedLongTy;
+  case Builtin::BI__builtin_umulll_overflow:
+  case Builtin::BI__builtin_usubll_overflow:
+  case Builtin::BI__builtin_uaddll_overflow:
+return Ast.UnsignedLongLongTy;
+  case Builtin::BI__builtin_mul_overflow:
+  case Builtin::BI__builtin_sub_overflow:
+  case Builtin::BI__builtin_add_overflow:
+return getOverflowBuiltinResultType(Call);
+  default:
+assert(false && "Unknown overflow builtin");
+  }
+}
+
 class BuiltinFunctionChecker : public Checker {
 public:
   bool evalCall(const CallEvent &Call, CheckerContext &C) const;
+  void HandleOverflowBuiltin(const CallEvent &Call, CheckerContext &C,
+ BinaryOperator::Opcode Op,
+ QualType ResultType) const;
 
 private:
   // From: clang/include/clang/Basic/Builtins.def
@@ -50,6 +101,44 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+void BuiltinFunctionChecker::HandleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // All __builtin_*_overflow functions take 3 argumets.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  // TODO: Handle overflows with values that known to overflow. Like INT_MAX + 
1
+  // should not produce state for non-overflow case and threat it as
+  // unreachable.
+
+  // Handle non-overflow case.
+  {
+ProgramStateRef StateSuccess =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs())
+  StateSuccess = StateSuccess->bindLoc(*L, RetVal, C.getLocationContext());
+
+C.addTransition(StateSuccess);
+  }
+
+  // Handle overflow case.
+  {
+C.addTransition(
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(true)));
+  }
+}
+
 bool BuiltinFunctionChecker::isBuiltinLikeFunction(
 const CallEvent &Call) const {
   const auto *FD = llvm::dyn_cast_or_null(Call.getDecl());
@@ -82,10 +171,41 @@ bool BuiltinFunctionC

[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

https://github.com/steakhal approved this pull request.

Still LGTM

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Donát Nagy via cfe-commits]

https://github.com/NagyDonat approved this pull request.

Also LGTM, sorry for not responding earlier. I agree with the minor suggestions 
of @steakhal .

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Donát Nagy via cfe-commits]

https://github.com/NagyDonat edited 
https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Donát Nagy via cfe-commits]

@@ -16,21 +16,93 @@
 
 #include "clang/Basic/Builtins.h"
 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
+#include "clang/StaticAnalyzer/Checkers/Taint.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 
 using namespace clang;
 using namespace ento;
+using namespace taint;
 
 namespace {
 
+QualType getSufficientTypeForOverflowOp(CheckerContext &C, const QualType &T) {
+  // Calling a builtin with a non-integer type result produces compiler error.
+  assert(T->isIntegerType());
+
+  ASTContext &ACtx = C.getASTContext();
+
+  unsigned BitWidth = ACtx.getIntWidth(T);
+  return ACtx.getIntTypeForBitwidth(BitWidth * 2, T->isSignedIntegerType());

NagyDonat wrote:

That's good enough for practical purposes. I guess that perhaps we could get an 
incorrect result in some weird corner case, but I don't think that it'll appear 
in real-world code.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Donát Nagy via cfe-commits]

@@ -0,0 +1,30 @@
+// RUN: %clang_analyze_cc1 -analyzer-checker=core -analyzer-output text \
+// RUN:   -verify %s
+
+void test_no_overflow_note(int a, int b)
+{
+   int res;
+
+   if (__builtin_add_overflow(a, b, &res)) // expected-note {{Assuming 
overflow does not happen}}

NagyDonat wrote:

I agree that the phrasing suggested by @steakhal would be better, but I think 
that the original is also acceptable.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

@@ -50,6 +122,107 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+const NoteTag *BuiltinFunctionChecker::createBuiltinNoOverflowNoteTag(
+CheckerContext &C, bool bothFeasible, SVal Arg1, SVal Arg2,
+SVal Result) const {
+  return C.getNoteTag([Result, Arg1, Arg2, bothFeasible](
+  PathSensitiveBugReport &BR, llvm::raw_ostream &OS) {
+if (!BR.isInteresting(Result))
+  return;
+
+// Propagate interestingness to input argumets if result is interesting.
+BR.markInteresting(Arg1);
+BR.markInteresting(Arg2);
+
+if (bothFeasible)
+  OS << "Assuming overflow does not happen";
+  });
+}
+
+const NoteTag *
+BuiltinFunctionChecker::createBuiltinOverflowNoteTag(CheckerContext &C) const {
+  return C.getNoteTag(
+  [](PathSensitiveBugReport &BR, llvm::raw_ostream &OS) {
+OS << "Assuming overflow does happen";
+  },
+  /*isPrunable=*/true);
+}
+
+std::pair
+BuiltinFunctionChecker::checkOverflow(CheckerContext &C, SVal RetVal,
+  QualType Res) const {
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  ASTContext &ACtx = C.getASTContext();
+
+  // Calling a builtin with a non-integer type result produces compiler error.
+  assert(Res->isIntegerType());
+
+  unsigned BitWidth = ACtx.getIntWidth(Res);
+  auto MinVal =
+  llvm::APSInt::getMinValue(BitWidth, Res->isUnsignedIntegerType());
+  auto MaxVal =
+  llvm::APSInt::getMaxValue(BitWidth, Res->isUnsignedIntegerType());
+
+  SVal IsLeMax =
+  SVB.evalBinOp(State, BO_LE, RetVal, nonloc::ConcreteInt(MaxVal), Res);
+  SVal IsGeMin =
+  SVB.evalBinOp(State, BO_GE, RetVal, nonloc::ConcreteInt(MinVal), Res);
+
+  auto [MayNotOverflow, MayOverflow] =
+  State->assume(IsLeMax.castAs());
+  auto [MayNotUnderflow, MayUnderflow] =
+  State->assume(IsGeMin.castAs());
+
+  return {MayOverflow || MayUnderflow, MayNotOverflow && MayNotUnderflow};
+}
+
+void BuiltinFunctionChecker::handleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // Calling a builtin with an incorrect argument count produces compiler 
error.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetValMax = SVB.evalBinOp(State, Op, Arg1, Arg2,
+ getSufficientTypeForOverflowOp(C, 
ResultType));
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  auto [Overflow, NotOverflow] = checkOverflow(C, RetValMax, ResultType);
+  if (NotOverflow) {
+ProgramStateRef StateNoOverflow =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs()) {
+  StateNoOverflow =
+  StateNoOverflow->bindLoc(*L, RetVal, C.getLocationContext());
+
+  // Propagate taint if any of the argumets were tainted
+  if (isTainted(State, Arg1) || isTainted(State, Arg2))
+StateNoOverflow = addTaint(StateNoOverflow, *L);
+}
+
+const NoteTag *tag = createBuiltinNoOverflowNoteTag(
+C, NotOverflow && Overflow, Arg1, Arg2, RetVal);

steakhal wrote:

```suggestion
C, /*BothFeasible=*/NotOverflow && Overflow, Arg1, Arg2, RetVal);
```

Maybe we could just invoke this fn directly in the `addTransition` call - 
unless that would break the lines in an ugly way.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

@@ -50,6 +101,44 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+void BuiltinFunctionChecker::HandleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // All __builtin_*_overflow functions take 3 argumets.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  // TODO: Handle overflows with values that known to overflow. Like INT_MAX + 
1
+  // should not produce state for non-overflow case and threat it as

steakhal wrote:

I thought the ConstraintAssignor does the decomposition of the SymSymExpr and 
tracks the potential value range. It's probably somewhat limited though.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

@@ -50,6 +122,107 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+const NoteTag *BuiltinFunctionChecker::createBuiltinNoOverflowNoteTag(
+CheckerContext &C, bool bothFeasible, SVal Arg1, SVal Arg2,
+SVal Result) const {
+  return C.getNoteTag([Result, Arg1, Arg2, bothFeasible](
+  PathSensitiveBugReport &BR, llvm::raw_ostream &OS) {
+if (!BR.isInteresting(Result))
+  return;
+
+// Propagate interestingness to input argumets if result is interesting.
+BR.markInteresting(Arg1);
+BR.markInteresting(Arg2);
+
+if (bothFeasible)
+  OS << "Assuming overflow does not happen";
+  });
+}
+
+const NoteTag *
+BuiltinFunctionChecker::createBuiltinOverflowNoteTag(CheckerContext &C) const {
+  return C.getNoteTag(
+  [](PathSensitiveBugReport &BR, llvm::raw_ostream &OS) {
+OS << "Assuming overflow does happen";
+  },
+  /*isPrunable=*/true);
+}
+
+std::pair
+BuiltinFunctionChecker::checkOverflow(CheckerContext &C, SVal RetVal,
+  QualType Res) const {
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  ASTContext &ACtx = C.getASTContext();
+
+  // Calling a builtin with a non-integer type result produces compiler error.
+  assert(Res->isIntegerType());
+
+  unsigned BitWidth = ACtx.getIntWidth(Res);
+  auto MinVal =
+  llvm::APSInt::getMinValue(BitWidth, Res->isUnsignedIntegerType());
+  auto MaxVal =
+  llvm::APSInt::getMaxValue(BitWidth, Res->isUnsignedIntegerType());
+
+  SVal IsLeMax =
+  SVB.evalBinOp(State, BO_LE, RetVal, nonloc::ConcreteInt(MaxVal), Res);
+  SVal IsGeMin =
+  SVB.evalBinOp(State, BO_GE, RetVal, nonloc::ConcreteInt(MinVal), Res);
+
+  auto [MayNotOverflow, MayOverflow] =
+  State->assume(IsLeMax.castAs());
+  auto [MayNotUnderflow, MayUnderflow] =
+  State->assume(IsGeMin.castAs());
+
+  return {MayOverflow || MayUnderflow, MayNotOverflow && MayNotUnderflow};
+}
+
+void BuiltinFunctionChecker::handleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // Calling a builtin with an incorrect argument count produces compiler 
error.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetValMax = SVB.evalBinOp(State, Op, Arg1, Arg2,
+ getSufficientTypeForOverflowOp(C, 
ResultType));
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  auto [Overflow, NotOverflow] = checkOverflow(C, RetValMax, ResultType);
+  if (NotOverflow) {
+ProgramStateRef StateNoOverflow =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs()) {
+  StateNoOverflow =
+  StateNoOverflow->bindLoc(*L, RetVal, C.getLocationContext());
+
+  // Propagate taint if any of the argumets were tainted
+  if (isTainted(State, Arg1) || isTainted(State, Arg2))
+StateNoOverflow = addTaint(StateNoOverflow, *L);
+}
+
+const NoteTag *tag = createBuiltinNoOverflowNoteTag(
+C, NotOverflow && Overflow, Arg1, Arg2, RetVal);
+
+C.addTransition(StateNoOverflow, tag);
+  }
+
+  if (Overflow) {
+const NoteTag *tag = createBuiltinOverflowNoteTag(C);
+C.addTransition(
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(true)),
+tag);

steakhal wrote:

```suggestion
C.addTransition(
State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(true)),
createBuiltinOverflowNoteTag(C));
```
I didn't see much value in having the tag in a separated statement.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

@@ -50,6 +122,107 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+const NoteTag *BuiltinFunctionChecker::createBuiltinNoOverflowNoteTag(
+CheckerContext &C, bool bothFeasible, SVal Arg1, SVal Arg2,
+SVal Result) const {
+  return C.getNoteTag([Result, Arg1, Arg2, bothFeasible](
+  PathSensitiveBugReport &BR, llvm::raw_ostream &OS) {
+if (!BR.isInteresting(Result))
+  return;
+
+// Propagate interestingness to input argumets if result is interesting.
+BR.markInteresting(Arg1);
+BR.markInteresting(Arg2);
+
+if (bothFeasible)
+  OS << "Assuming overflow does not happen";
+  });
+}
+
+const NoteTag *
+BuiltinFunctionChecker::createBuiltinOverflowNoteTag(CheckerContext &C) const {
+  return C.getNoteTag(
+  [](PathSensitiveBugReport &BR, llvm::raw_ostream &OS) {
+OS << "Assuming overflow does happen";
+  },
+  /*isPrunable=*/true);
+}
+
+std::pair
+BuiltinFunctionChecker::checkOverflow(CheckerContext &C, SVal RetVal,
+  QualType Res) const {
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  ASTContext &ACtx = C.getASTContext();
+
+  // Calling a builtin with a non-integer type result produces compiler error.
+  assert(Res->isIntegerType());
+
+  unsigned BitWidth = ACtx.getIntWidth(Res);
+  auto MinVal =
+  llvm::APSInt::getMinValue(BitWidth, Res->isUnsignedIntegerType());
+  auto MaxVal =
+  llvm::APSInt::getMaxValue(BitWidth, Res->isUnsignedIntegerType());
+
+  SVal IsLeMax =
+  SVB.evalBinOp(State, BO_LE, RetVal, nonloc::ConcreteInt(MaxVal), Res);
+  SVal IsGeMin =
+  SVB.evalBinOp(State, BO_GE, RetVal, nonloc::ConcreteInt(MinVal), Res);
+
+  auto [MayNotOverflow, MayOverflow] =
+  State->assume(IsLeMax.castAs());
+  auto [MayNotUnderflow, MayUnderflow] =
+  State->assume(IsGeMin.castAs());
+
+  return {MayOverflow || MayUnderflow, MayNotOverflow && MayNotUnderflow};

steakhal wrote:

```suggestion
  // Calling a builtin with a non-integer type result produces compiler error.
  assert(Res->isIntegerType());

  unsigned BitWidth = C.getASTContext().getIntWidth(Res);
  bool IsUnsigned = Res->isUnsignedIntegerType();

  nonloc::ConcreteInt MinVal{llvm::APSInt::getMinValue(BitWidth, IsUnsigned)};
  nonloc::ConcreteInt MaxVal{llvm::APSInt::getMaxValue(BitWidth, IsUnsigned)};

  SValBuilder &SVB = C.getSValBuilder();
  ProgramStateRef State = C.getState();
  SVal IsLeMax = SVB.evalBinOp(State, BO_LE, RetVal, MaxVal, Res);
  SVal IsGeMin = SVB.evalBinOp(State, BO_GE, RetVal, MinVal, Res);

  auto [MayNotOverflow, MayOverflow] =
  State->assume(IsLeMax.castAs());
  auto [MayNotUnderflow, MayUnderflow] =
  State->assume(IsGeMin.castAs());

  return {MayOverflow || MayUnderflow, MayNotOverflow && MayNotUnderflow};
```

Uh, the diff of this suggestion looks horrible even though I basically just 
reshuffled the lines to have a combination where the variable definitions are 
closer to their use, keep symmetry and try to prevent linebreaks.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

@@ -0,0 +1,157 @@
+// RUN: %clang_analyze_cc1 -triple x86_64-unknown-unknown -verify %s \
+// RUN:   -analyzer-checker=core,debug.ExprInspection
+
+#define __UINT_MAX__ (__INT_MAX__ * 2U + 1U)
+#define __INT_MIN__  (-__INT_MAX__ - 1)
+
+void clang_analyzer_dump_int(int);
+void clang_analyzer_dump_long(long);
+void clang_analyzer_eval(int);
+void clang_analyzer_warnIfReached(void);
+
+void test_add_nooverflow(void)
+{
+   int res;
+
+   if (__builtin_add_overflow(10, 20, &res)) {
+ clang_analyzer_warnIfReached();
+ return;
+   }
+
+   clang_analyzer_dump_int(res); //expected-warning{{30 S32b}}
+}
+
+void test_add_overflow(void)
+{
+   int res;
+
+   if (__builtin_add_overflow(__INT_MAX__, 1, &res)) {
+ clang_analyzer_dump_int(res); //expected-warning{{1st function call 
argument is an uninitialized value}}
+ return;
+   }
+
+   clang_analyzer_warnIfReached();
+}
+
+void test_add_underoverflow(void)
+{
+   int res;
+
+   if (__builtin_add_overflow(__INT_MIN__, -1, &res)) {
+ clang_analyzer_dump_int(res); //expected-warning{{1st function call 
argument is an uninitialized value}}
+ return;
+   }
+
+   clang_analyzer_warnIfReached();
+}
+
+void test_sub_underflow(void)
+{
+   int res;
+
+   if (__builtin_sub_overflow(__INT_MIN__, 10, &res)) {
+ return;
+   }
+
+   clang_analyzer_warnIfReached();
+}
+
+void test_sub_overflow(void)
+{
+   int res;
+
+   if (__builtin_sub_overflow(__INT_MAX__, -1, &res)) {
+ return;
+   }
+
+   clang_analyzer_warnIfReached();
+}
+
+void test_sub_nooverflow(void)
+{
+   int res;
+
+   if (__builtin_sub_overflow(__INT_MAX__, 1, &res)) {
+ clang_analyzer_warnIfReached();
+ return;
+   }
+
+   clang_analyzer_dump_int(res); //expected-warning{{2147483646 S32b}}
+}
+
+void test_mul_overrflow(void)
+{
+   int res;
+
+   if (__builtin_mul_overflow(__INT_MAX__, 2, &res)) {
+ return;
+   }
+
+   clang_analyzer_warnIfReached();
+}
+
+void test_mul_underrflow(void)

steakhal wrote:

```suggestion
void test_mul_underflow(void)
```

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

@@ -50,6 +122,107 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+const NoteTag *BuiltinFunctionChecker::createBuiltinNoOverflowNoteTag(
+CheckerContext &C, bool bothFeasible, SVal Arg1, SVal Arg2,

steakhal wrote:

```suggestion
CheckerContext &C, bool BothFeasible, SVal Arg1, SVal Arg2,
```

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

@@ -0,0 +1,30 @@
+// RUN: %clang_analyze_cc1 -analyzer-checker=core -analyzer-output text \
+// RUN:   -verify %s
+
+void test_no_overflow_note(int a, int b)
+{
+   int res;
+
+   if (__builtin_add_overflow(a, b, &res)) // expected-note {{Assuming 
overflow does not happen}}

steakhal wrote:

Maybe it's just me, but I find this phrasing a bit weird.
To me it would read a lot more natural if it was `Assuming overflow` or 
`Assuming no overflow`. Maybe suffixed with `... happens`.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

@@ -16,21 +16,93 @@
 
 #include "clang/Basic/Builtins.h"
 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
+#include "clang/StaticAnalyzer/Checkers/Taint.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 
 using namespace clang;
 using namespace ento;
+using namespace taint;
 
 namespace {
 
+QualType getSufficientTypeForOverflowOp(CheckerContext &C, const QualType &T) {
+  // Calling a builtin with a non-integer type result produces compiler error.
+  assert(T->isIntegerType());
+
+  ASTContext &ACtx = C.getASTContext();
+
+  unsigned BitWidth = ACtx.getIntWidth(T);
+  return ACtx.getIntTypeForBitwidth(BitWidth * 2, T->isSignedIntegerType());
+}
+
+QualType getOverflowBuiltinResultType(const CallEvent &Call) {
+  // Calling a builtin with an incorrect argument count produces compiler 
error.
+  assert(Call.getNumArgs() == 3);
+
+  return Call.getArgExpr(2)->getType()->getPointeeType();
+}
+
+QualType getOverflowBuiltinResultType(const CallEvent &Call, CheckerContext &C,
+  unsigned BI) {
+  // Calling a builtin with an incorrect argument count produces compiler 
error.
+  assert(Call.getNumArgs() == 3);
+
+  ASTContext &ACtx = C.getASTContext();
+
+  switch (BI) {
+  case Builtin::BI__builtin_smul_overflow:
+  case Builtin::BI__builtin_ssub_overflow:
+  case Builtin::BI__builtin_sadd_overflow:
+return ACtx.IntTy;
+  case Builtin::BI__builtin_smull_overflow:
+  case Builtin::BI__builtin_ssubl_overflow:
+  case Builtin::BI__builtin_saddl_overflow:
+return ACtx.LongTy;
+  case Builtin::BI__builtin_smulll_overflow:
+  case Builtin::BI__builtin_ssubll_overflow:
+  case Builtin::BI__builtin_saddll_overflow:
+return ACtx.LongLongTy;
+  case Builtin::BI__builtin_umul_overflow:
+  case Builtin::BI__builtin_usub_overflow:
+  case Builtin::BI__builtin_uadd_overflow:
+return ACtx.UnsignedIntTy;
+  case Builtin::BI__builtin_umull_overflow:
+  case Builtin::BI__builtin_usubl_overflow:
+  case Builtin::BI__builtin_uaddl_overflow:
+return ACtx.UnsignedLongTy;
+  case Builtin::BI__builtin_umulll_overflow:
+  case Builtin::BI__builtin_usubll_overflow:
+  case Builtin::BI__builtin_uaddll_overflow:
+return ACtx.UnsignedLongLongTy;
+  case Builtin::BI__builtin_mul_overflow:
+  case Builtin::BI__builtin_sub_overflow:
+  case Builtin::BI__builtin_add_overflow:
+return getOverflowBuiltinResultType(Call);
+  default:
+assert(false && "Unknown overflow builtin");
+return ACtx.IntTy;
+  }
+}
+
 class BuiltinFunctionChecker : public Checker {
 public:
   bool evalCall(const CallEvent &Call, CheckerContext &C) const;
+  void handleOverflowBuiltin(const CallEvent &Call, CheckerContext &C,
+ BinaryOperator::Opcode Op,
+ QualType ResultType) const;
+  const NoteTag *createBuiltinNoOverflowNoteTag(CheckerContext &C,
+bool bothFeasible, SVal Arg1,

steakhal wrote:

```suggestion
bool BothFeasible, SVal Arg1,
```

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

@@ -327,6 +327,8 @@ Static Analyzer
 New features
 
 
+- Now CSA models `__builtin_*_overflow` functions.

steakhal wrote:

```suggestion
- Now CSA models `__builtin_*_overflow` functions. (#GH102602)
```

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

https://github.com/steakhal edited 
https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

https://github.com/steakhal approved this pull request.

Looks fantastic! I have no functional remarks. I only sprinkled it with some 
nits, but other than those it's perfect.
It's already good, I'll let you decide if you want to do the final touches or 
not as those may be more subjective suggestions.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

@@ -0,0 +1,157 @@
+// RUN: %clang_analyze_cc1 -triple x86_64-unknown-unknown -verify %s \
+// RUN:   -analyzer-checker=core,debug.ExprInspection
+
+#define __UINT_MAX__ (__INT_MAX__ * 2U + 1U)
+#define __INT_MIN__  (-__INT_MAX__ - 1)
+
+void clang_analyzer_dump_int(int);
+void clang_analyzer_dump_long(long);
+void clang_analyzer_eval(int);
+void clang_analyzer_warnIfReached(void);
+
+void test_add_nooverflow(void)
+{
+   int res;
+
+   if (__builtin_add_overflow(10, 20, &res)) {
+ clang_analyzer_warnIfReached();
+ return;
+   }
+
+   clang_analyzer_dump_int(res); //expected-warning{{30 S32b}}
+}
+
+void test_add_overflow(void)
+{
+   int res;
+
+   if (__builtin_add_overflow(__INT_MAX__, 1, &res)) {
+ clang_analyzer_dump_int(res); //expected-warning{{1st function call 
argument is an uninitialized value}}
+ return;
+   }
+
+   clang_analyzer_warnIfReached();
+}
+
+void test_add_underoverflow(void)
+{
+   int res;
+
+   if (__builtin_add_overflow(__INT_MIN__, -1, &res)) {
+ clang_analyzer_dump_int(res); //expected-warning{{1st function call 
argument is an uninitialized value}}
+ return;
+   }
+
+   clang_analyzer_warnIfReached();
+}
+
+void test_sub_underflow(void)
+{
+   int res;
+
+   if (__builtin_sub_overflow(__INT_MIN__, 10, &res)) {
+ return;
+   }
+
+   clang_analyzer_warnIfReached();
+}
+
+void test_sub_overflow(void)
+{
+   int res;
+
+   if (__builtin_sub_overflow(__INT_MAX__, -1, &res)) {
+ return;
+   }
+
+   clang_analyzer_warnIfReached();
+}
+
+void test_sub_nooverflow(void)
+{
+   int res;
+
+   if (__builtin_sub_overflow(__INT_MAX__, 1, &res)) {
+ clang_analyzer_warnIfReached();
+ return;
+   }
+
+   clang_analyzer_dump_int(res); //expected-warning{{2147483646 S32b}}
+}
+
+void test_mul_overrflow(void)

steakhal wrote:

```suggestion
void test_mul_overflow(void)
```

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

pskrgag wrote:

gentle ping 

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

https://github.com/pskrgag updated 
https://github.com/llvm/llvm-project/pull/102602

>From 7b4f999b39f4308cab253204e6be41ea7a70f695 Mon Sep 17 00:00:00 2001
From: Pavel Skripkin 
Date: Fri, 9 Aug 2024 14:37:47 +0300
Subject: [PATCH 01/10] clang/csa: add initial support for builtin overflow

---
 .../Checkers/BuiltinFunctionChecker.cpp   | 124 +-
 clang/test/Analysis/builtin_overflow.c|  65 +
 .../test/Analysis/out-of-bounds-diagnostics.c |  17 +++
 3 files changed, 204 insertions(+), 2 deletions(-)
 create mode 100644 clang/test/Analysis/builtin_overflow.c

diff --git a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp 
b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
index b198b1c2ff4d11..0c8b9fa3d947b0 100644
--- a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
+++ b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
@@ -21,16 +21,67 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 
+QualType getOverflowBuiltinResultType(const CallEvent &Call) {
+  assert(Call.getNumArgs() == 3);
+
+  return Call.getArgExpr(2)->getType()->getPointeeType();
+}
+
+QualType getOverflowBuiltinResultType(const CallEvent &Call, CheckerContext &C,
+  unsigned BI) {
+  assert(Call.getNumArgs() == 3);
+
+  ASTContext &Ast = C.getASTContext();
+
+  switch (BI) {
+  case Builtin::BI__builtin_smul_overflow:
+  case Builtin::BI__builtin_ssub_overflow:
+  case Builtin::BI__builtin_sadd_overflow:
+return Ast.IntTy;
+  case Builtin::BI__builtin_smull_overflow:
+  case Builtin::BI__builtin_ssubl_overflow:
+  case Builtin::BI__builtin_saddl_overflow:
+return Ast.LongTy;
+  case Builtin::BI__builtin_smulll_overflow:
+  case Builtin::BI__builtin_ssubll_overflow:
+  case Builtin::BI__builtin_saddll_overflow:
+return Ast.LongLongTy;
+  case Builtin::BI__builtin_umul_overflow:
+  case Builtin::BI__builtin_usub_overflow:
+  case Builtin::BI__builtin_uadd_overflow:
+return Ast.UnsignedIntTy;
+  case Builtin::BI__builtin_umull_overflow:
+  case Builtin::BI__builtin_usubl_overflow:
+  case Builtin::BI__builtin_uaddl_overflow:
+return Ast.UnsignedLongTy;
+  case Builtin::BI__builtin_umulll_overflow:
+  case Builtin::BI__builtin_usubll_overflow:
+  case Builtin::BI__builtin_uaddll_overflow:
+return Ast.UnsignedLongLongTy;
+  case Builtin::BI__builtin_mul_overflow:
+  case Builtin::BI__builtin_sub_overflow:
+  case Builtin::BI__builtin_add_overflow:
+return getOverflowBuiltinResultType(Call);
+  default:
+assert(false && "Unknown overflow builtin");
+  }
+}
+
 class BuiltinFunctionChecker : public Checker {
 public:
   bool evalCall(const CallEvent &Call, CheckerContext &C) const;
+  void HandleOverflowBuiltin(const CallEvent &Call, CheckerContext &C,
+ BinaryOperator::Opcode Op,
+ QualType ResultType) const;
 
 private:
   // From: clang/include/clang/Basic/Builtins.def
@@ -50,6 +101,44 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+void BuiltinFunctionChecker::HandleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // All __builtin_*_overflow functions take 3 argumets.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  // TODO: Handle overflows with values that known to overflow. Like INT_MAX + 
1
+  // should not produce state for non-overflow case and threat it as
+  // unreachable.
+
+  // Handle non-overflow case.
+  {
+ProgramStateRef StateSuccess =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs())
+  StateSuccess = StateSuccess->bindLoc(*L, RetVal, C.getLocationContext());
+
+C.addTransition(StateSuccess);
+  }
+
+  // Handle overflow case.
+  {
+C.addTransition(
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(true)));
+  }
+}
+
 bool BuiltinFunctionChecker::isBuiltinLikeFunction(
 const CallEvent &Call) const {
   const auto *FD = llvm::dyn_cast_or_null(Call.getDecl());
@@ -82,10 +171,41 @@ bool BuiltinFunctionC

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

@@ -16,21 +16,93 @@
 
 #include "clang/Basic/Builtins.h"
 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
+#include "clang/StaticAnalyzer/Checkers/Taint.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 
 using namespace clang;
 using namespace ento;
+using namespace taint;
 
 namespace {
 
+QualType getSufficientTypeForOverflowOp(CheckerContext &C, const QualType &T) {
+  // Calling a builtin with a non-integer type result produces compiler error.
+  assert(T->isIntegerType());
+
+  ASTContext &ACtx = C.getASTContext();
+
+  unsigned BitWidth = ACtx.getIntWidth(T);
+  return ACtx.getIntTypeForBitwidth(BitWidth * 2, T->isSignedIntegerType());

pskrgag wrote:

Based on `getIntTypeForBitwith` source, it just returns `128` bit ingetegers 
and does not crash:

```cpp
  if (!QualTy && DestWidth == 128)
return Signed ? Int128Ty : UnsignedInt128Ty;
```

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Donát Nagy via cfe-commits]

@@ -16,21 +16,93 @@
 
 #include "clang/Basic/Builtins.h"
 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
+#include "clang/StaticAnalyzer/Checkers/Taint.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 
 using namespace clang;
 using namespace ento;
+using namespace taint;
 
 namespace {
 
+QualType getSufficientTypeForOverflowOp(CheckerContext &C, const QualType &T) {
+  // Calling a builtin with a non-integer type result produces compiler error.
+  assert(T->isIntegerType());
+
+  ASTContext &ACtx = C.getASTContext();
+
+  unsigned BitWidth = ACtx.getIntWidth(T);
+  return ACtx.getIntTypeForBitwidth(BitWidth * 2, T->isSignedIntegerType());

NagyDonat wrote:

What happens if `BitWidth * 2` is too large and there is no standard / 
semi-standard (like `__int128`) type to represent it? Do we get a compiler 
error at an earlier step? Does this call crash?

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Donát Nagy via cfe-commits]

@@ -327,6 +327,8 @@ Static Analyzer
 New features
 
 
+- Now CSA models `builtin_*_overflow` functions.

NagyDonat wrote:

```suggestion
- Now CSA models `__builtin_*_overflow` functions.
```

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Donát Nagy via cfe-commits]

https://github.com/NagyDonat edited 
https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Donát Nagy via cfe-commits]

https://github.com/NagyDonat commented:

I re-reviewed the commit and added two very minor remarks, otherwise LGTM.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

pskrgag wrote:

Hello!

Is there anything else that stops this PR? Thanks!

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

@@ -50,6 +118,75 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+std::pair
+BuiltinFunctionChecker::checkOverflow(CheckerContext &C, SVal RetVal,
+  QualType Res) const {
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  ASTContext &ACtx = C.getASTContext();
+
+  // Calling a builtin with a non-integer type result produces compiler error.
+  assert(Res->isIntegerType());
+
+  unsigned BitWidth = ACtx.getIntWidth(Res);
+  auto MinVal =
+  llvm::APSInt::getMinValue(BitWidth, Res->isUnsignedIntegerType());
+  auto MaxVal =
+  llvm::APSInt::getMaxValue(BitWidth, Res->isUnsignedIntegerType());
+
+  SVal IsLeMax =
+  SVB.evalBinOp(State, BO_LE, RetVal, nonloc::ConcreteInt(MaxVal), Res);
+  SVal IsGeMin =
+  SVB.evalBinOp(State, BO_GE, RetVal, nonloc::ConcreteInt(MinVal), Res);
+
+  auto [MayNotOverflow, MayOverflow] =
+  State->assume(IsLeMax.castAs());
+  auto [MayNotUnderflow, MayUnderflow] =
+  State->assume(IsGeMin.castAs());
+
+  return {MayOverflow || MayUnderflow, MayNotOverflow && MayNotUnderflow};
+}
+
+void BuiltinFunctionChecker::handleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // Calling a builtin with an incorrect argument count produces compiler 
error.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetValMax = SVB.evalBinOp(State, Op, Arg1, Arg2,
+ getSufficientTypeForOverflowOp(C, 
ResultType));
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  auto [Overflow, NotOverflow] = checkOverflow(C, RetValMax, ResultType);
+  if (NotOverflow) {
+ProgramStateRef StateNoOverflow =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs()) {
+  StateNoOverflow =
+  StateNoOverflow->bindLoc(*L, RetVal, C.getLocationContext());
+
+  // Propagate taint if any of the argumets were tainted
+  if (isTainted(State, Arg1) || isTainted(State, Arg2))
+StateNoOverflow = addTaint(StateNoOverflow, *L);
+}
+
+C.addTransition(StateNoOverflow);

pskrgag wrote:

Added notes for overflow case with prunable flag in the latest version, thanks!

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

https://github.com/pskrgag updated 
https://github.com/llvm/llvm-project/pull/102602

>From 7b4f999b39f4308cab253204e6be41ea7a70f695 Mon Sep 17 00:00:00 2001
From: Pavel Skripkin 
Date: Fri, 9 Aug 2024 14:37:47 +0300
Subject: [PATCH 1/9] clang/csa: add initial support for builtin overflow

---
 .../Checkers/BuiltinFunctionChecker.cpp   | 124 +-
 clang/test/Analysis/builtin_overflow.c|  65 +
 .../test/Analysis/out-of-bounds-diagnostics.c |  17 +++
 3 files changed, 204 insertions(+), 2 deletions(-)
 create mode 100644 clang/test/Analysis/builtin_overflow.c

diff --git a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp 
b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
index b198b1c2ff4d11..0c8b9fa3d947b0 100644
--- a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
+++ b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
@@ -21,16 +21,67 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 
+QualType getOverflowBuiltinResultType(const CallEvent &Call) {
+  assert(Call.getNumArgs() == 3);
+
+  return Call.getArgExpr(2)->getType()->getPointeeType();
+}
+
+QualType getOverflowBuiltinResultType(const CallEvent &Call, CheckerContext &C,
+  unsigned BI) {
+  assert(Call.getNumArgs() == 3);
+
+  ASTContext &Ast = C.getASTContext();
+
+  switch (BI) {
+  case Builtin::BI__builtin_smul_overflow:
+  case Builtin::BI__builtin_ssub_overflow:
+  case Builtin::BI__builtin_sadd_overflow:
+return Ast.IntTy;
+  case Builtin::BI__builtin_smull_overflow:
+  case Builtin::BI__builtin_ssubl_overflow:
+  case Builtin::BI__builtin_saddl_overflow:
+return Ast.LongTy;
+  case Builtin::BI__builtin_smulll_overflow:
+  case Builtin::BI__builtin_ssubll_overflow:
+  case Builtin::BI__builtin_saddll_overflow:
+return Ast.LongLongTy;
+  case Builtin::BI__builtin_umul_overflow:
+  case Builtin::BI__builtin_usub_overflow:
+  case Builtin::BI__builtin_uadd_overflow:
+return Ast.UnsignedIntTy;
+  case Builtin::BI__builtin_umull_overflow:
+  case Builtin::BI__builtin_usubl_overflow:
+  case Builtin::BI__builtin_uaddl_overflow:
+return Ast.UnsignedLongTy;
+  case Builtin::BI__builtin_umulll_overflow:
+  case Builtin::BI__builtin_usubll_overflow:
+  case Builtin::BI__builtin_uaddll_overflow:
+return Ast.UnsignedLongLongTy;
+  case Builtin::BI__builtin_mul_overflow:
+  case Builtin::BI__builtin_sub_overflow:
+  case Builtin::BI__builtin_add_overflow:
+return getOverflowBuiltinResultType(Call);
+  default:
+assert(false && "Unknown overflow builtin");
+  }
+}
+
 class BuiltinFunctionChecker : public Checker {
 public:
   bool evalCall(const CallEvent &Call, CheckerContext &C) const;
+  void HandleOverflowBuiltin(const CallEvent &Call, CheckerContext &C,
+ BinaryOperator::Opcode Op,
+ QualType ResultType) const;
 
 private:
   // From: clang/include/clang/Basic/Builtins.def
@@ -50,6 +101,44 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+void BuiltinFunctionChecker::HandleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // All __builtin_*_overflow functions take 3 argumets.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  // TODO: Handle overflows with values that known to overflow. Like INT_MAX + 
1
+  // should not produce state for non-overflow case and threat it as
+  // unreachable.
+
+  // Handle non-overflow case.
+  {
+ProgramStateRef StateSuccess =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs())
+  StateSuccess = StateSuccess->bindLoc(*L, RetVal, C.getLocationContext());
+
+C.addTransition(StateSuccess);
+  }
+
+  // Handle overflow case.
+  {
+C.addTransition(
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(true)));
+  }
+}
+
 bool BuiltinFunctionChecker::isBuiltinLikeFunction(
 const CallEvent &Call) const {
   const auto *FD = llvm::dyn_cast_or_null(Call.getDecl());
@@ -82,10 +171,41 @@ bool BuiltinFunctionChe

[clang] [analyzer] Model overflow builtins (PR #102602)

[Donát Nagy via cfe-commits]

@@ -50,6 +118,75 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+std::pair
+BuiltinFunctionChecker::checkOverflow(CheckerContext &C, SVal RetVal,
+  QualType Res) const {
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  ASTContext &ACtx = C.getASTContext();
+
+  // Calling a builtin with a non-integer type result produces compiler error.
+  assert(Res->isIntegerType());
+
+  unsigned BitWidth = ACtx.getIntWidth(Res);
+  auto MinVal =
+  llvm::APSInt::getMinValue(BitWidth, Res->isUnsignedIntegerType());
+  auto MaxVal =
+  llvm::APSInt::getMaxValue(BitWidth, Res->isUnsignedIntegerType());
+
+  SVal IsLeMax =
+  SVB.evalBinOp(State, BO_LE, RetVal, nonloc::ConcreteInt(MaxVal), Res);
+  SVal IsGeMin =
+  SVB.evalBinOp(State, BO_GE, RetVal, nonloc::ConcreteInt(MinVal), Res);
+
+  auto [MayNotOverflow, MayOverflow] =
+  State->assume(IsLeMax.castAs());
+  auto [MayNotUnderflow, MayUnderflow] =
+  State->assume(IsGeMin.castAs());
+
+  return {MayOverflow || MayUnderflow, MayNotOverflow && MayNotUnderflow};
+}
+
+void BuiltinFunctionChecker::handleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // Calling a builtin with an incorrect argument count produces compiler 
error.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetValMax = SVB.evalBinOp(State, Op, Arg1, Arg2,
+ getSufficientTypeForOverflowOp(C, 
ResultType));
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  auto [Overflow, NotOverflow] = checkOverflow(C, RetValMax, ResultType);
+  if (NotOverflow) {
+ProgramStateRef StateNoOverflow =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs()) {
+  StateNoOverflow =
+  StateNoOverflow->bindLoc(*L, RetVal, C.getLocationContext());
+
+  // Propagate taint if any of the argumets were tainted
+  if (isTainted(State, Arg1) || isTainted(State, Arg2))
+StateNoOverflow = addTaint(StateNoOverflow, *L);
+}
+
+C.addTransition(StateNoOverflow);

NagyDonat wrote:

Oh I see... the undefined rvalue within `res` is represented by an 
`UndefinedVal`, which is not symbolic (does not have a unique identity, unlike 
e.g. `nonloc::SymbolVal`), so we cannot mark it as interesting, because it does 
not have an associated symbol.

Either always display the "Assuming overflow happens" note (it is a surprising 
case that's worth some highlight and with `IsPrunable` set to true it won't be 
_too_ spammy), or leave this as-is for now and perhaps return with a better 
solution in a follow-up  commit.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

@@ -50,6 +118,75 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+std::pair
+BuiltinFunctionChecker::checkOverflow(CheckerContext &C, SVal RetVal,
+  QualType Res) const {
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  ASTContext &ACtx = C.getASTContext();
+
+  // Calling a builtin with a non-integer type result produces compiler error.
+  assert(Res->isIntegerType());
+
+  unsigned BitWidth = ACtx.getIntWidth(Res);
+  auto MinVal =
+  llvm::APSInt::getMinValue(BitWidth, Res->isUnsignedIntegerType());
+  auto MaxVal =
+  llvm::APSInt::getMaxValue(BitWidth, Res->isUnsignedIntegerType());
+
+  SVal IsLeMax =
+  SVB.evalBinOp(State, BO_LE, RetVal, nonloc::ConcreteInt(MaxVal), Res);
+  SVal IsGeMin =
+  SVB.evalBinOp(State, BO_GE, RetVal, nonloc::ConcreteInt(MinVal), Res);
+
+  auto [MayNotOverflow, MayOverflow] =
+  State->assume(IsLeMax.castAs());
+  auto [MayNotUnderflow, MayUnderflow] =
+  State->assume(IsGeMin.castAs());
+
+  return {MayOverflow || MayUnderflow, MayNotOverflow && MayNotUnderflow};
+}
+
+void BuiltinFunctionChecker::handleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // Calling a builtin with an incorrect argument count produces compiler 
error.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetValMax = SVB.evalBinOp(State, Op, Arg1, Arg2,
+ getSufficientTypeForOverflowOp(C, 
ResultType));
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  auto [Overflow, NotOverflow] = checkOverflow(C, RetValMax, ResultType);
+  if (NotOverflow) {
+ProgramStateRef StateNoOverflow =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs()) {
+  StateNoOverflow =
+  StateNoOverflow->bindLoc(*L, RetVal, C.getLocationContext());
+
+  // Propagate taint if any of the argumets were tainted
+  if (isTainted(State, Arg1) || isTainted(State, Arg2))
+StateNoOverflow = addTaint(StateNoOverflow, *L);
+}
+
+C.addTransition(StateNoOverflow);

pskrgag wrote:

> Oops, I wanted to refer to the result of the operation (which is written to 
> the memory area specified by the third argument), not the boolean "did 
> overflow happen?"

Yes, that was clear and I implemented it in the lasted version, but anyway in 
case of say

```c
int res;
if (__builtin_add_oveflow(a, b, &res))
   doStmh(res); // <-- read of uninit value
``` 

`res` is somehow not interesting... =(

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Donát Nagy via cfe-commits]

https://github.com/NagyDonat edited 
https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Donát Nagy via cfe-commits]

@@ -50,6 +118,75 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+std::pair
+BuiltinFunctionChecker::checkOverflow(CheckerContext &C, SVal RetVal,
+  QualType Res) const {
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  ASTContext &ACtx = C.getASTContext();
+
+  // Calling a builtin with a non-integer type result produces compiler error.
+  assert(Res->isIntegerType());
+
+  unsigned BitWidth = ACtx.getIntWidth(Res);
+  auto MinVal =
+  llvm::APSInt::getMinValue(BitWidth, Res->isUnsignedIntegerType());
+  auto MaxVal =
+  llvm::APSInt::getMaxValue(BitWidth, Res->isUnsignedIntegerType());
+
+  SVal IsLeMax =
+  SVB.evalBinOp(State, BO_LE, RetVal, nonloc::ConcreteInt(MaxVal), Res);
+  SVal IsGeMin =
+  SVB.evalBinOp(State, BO_GE, RetVal, nonloc::ConcreteInt(MinVal), Res);
+
+  auto [MayNotOverflow, MayOverflow] =
+  State->assume(IsLeMax.castAs());
+  auto [MayNotUnderflow, MayUnderflow] =
+  State->assume(IsGeMin.castAs());
+
+  return {MayOverflow || MayUnderflow, MayNotOverflow && MayNotUnderflow};
+}
+
+void BuiltinFunctionChecker::handleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // Calling a builtin with an incorrect argument count produces compiler 
error.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetValMax = SVB.evalBinOp(State, Op, Arg1, Arg2,
+ getSufficientTypeForOverflowOp(C, 
ResultType));
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  auto [Overflow, NotOverflow] = checkOverflow(C, RetValMax, ResultType);
+  if (NotOverflow) {
+ProgramStateRef StateNoOverflow =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs()) {
+  StateNoOverflow =
+  StateNoOverflow->bindLoc(*L, RetVal, C.getLocationContext());
+
+  // Propagate taint if any of the argumets were tainted
+  if (isTainted(State, Arg1) || isTainted(State, Arg2))
+StateNoOverflow = addTaint(StateNoOverflow, *L);
+}
+
+C.addTransition(StateNoOverflow);

NagyDonat wrote:

> if overflow happens, then result does not end up in InterestingSymbols in bug 
> reporter,

Oops, I wanted to refer to the _result of the operation_ (which is written to 
the memory area specified by the third argument), not the boolean "did overflow 
happen?" return value of the `__builitin_X_overflow()`. However, now that I 
think about this, we should display the note if either of these values are 
interesting.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

https://github.com/pskrgag updated 
https://github.com/llvm/llvm-project/pull/102602

>From 7b4f999b39f4308cab253204e6be41ea7a70f695 Mon Sep 17 00:00:00 2001
From: Pavel Skripkin 
Date: Fri, 9 Aug 2024 14:37:47 +0300
Subject: [PATCH 1/8] clang/csa: add initial support for builtin overflow

---
 .../Checkers/BuiltinFunctionChecker.cpp   | 124 +-
 clang/test/Analysis/builtin_overflow.c|  65 +
 .../test/Analysis/out-of-bounds-diagnostics.c |  17 +++
 3 files changed, 204 insertions(+), 2 deletions(-)
 create mode 100644 clang/test/Analysis/builtin_overflow.c

diff --git a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp 
b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
index b198b1c2ff4d11..0c8b9fa3d947b0 100644
--- a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
+++ b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
@@ -21,16 +21,67 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 
+QualType getOverflowBuiltinResultType(const CallEvent &Call) {
+  assert(Call.getNumArgs() == 3);
+
+  return Call.getArgExpr(2)->getType()->getPointeeType();
+}
+
+QualType getOverflowBuiltinResultType(const CallEvent &Call, CheckerContext &C,
+  unsigned BI) {
+  assert(Call.getNumArgs() == 3);
+
+  ASTContext &Ast = C.getASTContext();
+
+  switch (BI) {
+  case Builtin::BI__builtin_smul_overflow:
+  case Builtin::BI__builtin_ssub_overflow:
+  case Builtin::BI__builtin_sadd_overflow:
+return Ast.IntTy;
+  case Builtin::BI__builtin_smull_overflow:
+  case Builtin::BI__builtin_ssubl_overflow:
+  case Builtin::BI__builtin_saddl_overflow:
+return Ast.LongTy;
+  case Builtin::BI__builtin_smulll_overflow:
+  case Builtin::BI__builtin_ssubll_overflow:
+  case Builtin::BI__builtin_saddll_overflow:
+return Ast.LongLongTy;
+  case Builtin::BI__builtin_umul_overflow:
+  case Builtin::BI__builtin_usub_overflow:
+  case Builtin::BI__builtin_uadd_overflow:
+return Ast.UnsignedIntTy;
+  case Builtin::BI__builtin_umull_overflow:
+  case Builtin::BI__builtin_usubl_overflow:
+  case Builtin::BI__builtin_uaddl_overflow:
+return Ast.UnsignedLongTy;
+  case Builtin::BI__builtin_umulll_overflow:
+  case Builtin::BI__builtin_usubll_overflow:
+  case Builtin::BI__builtin_uaddll_overflow:
+return Ast.UnsignedLongLongTy;
+  case Builtin::BI__builtin_mul_overflow:
+  case Builtin::BI__builtin_sub_overflow:
+  case Builtin::BI__builtin_add_overflow:
+return getOverflowBuiltinResultType(Call);
+  default:
+assert(false && "Unknown overflow builtin");
+  }
+}
+
 class BuiltinFunctionChecker : public Checker {
 public:
   bool evalCall(const CallEvent &Call, CheckerContext &C) const;
+  void HandleOverflowBuiltin(const CallEvent &Call, CheckerContext &C,
+ BinaryOperator::Opcode Op,
+ QualType ResultType) const;
 
 private:
   // From: clang/include/clang/Basic/Builtins.def
@@ -50,6 +101,44 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+void BuiltinFunctionChecker::HandleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // All __builtin_*_overflow functions take 3 argumets.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  // TODO: Handle overflows with values that known to overflow. Like INT_MAX + 
1
+  // should not produce state for non-overflow case and threat it as
+  // unreachable.
+
+  // Handle non-overflow case.
+  {
+ProgramStateRef StateSuccess =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs())
+  StateSuccess = StateSuccess->bindLoc(*L, RetVal, C.getLocationContext());
+
+C.addTransition(StateSuccess);
+  }
+
+  // Handle overflow case.
+  {
+C.addTransition(
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(true)));
+  }
+}
+
 bool BuiltinFunctionChecker::isBuiltinLikeFunction(
 const CallEvent &Call) const {
   const auto *FD = llvm::dyn_cast_or_null(Call.getDecl());
@@ -82,10 +171,41 @@ bool BuiltinFunctionChe

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

@@ -50,6 +118,75 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+std::pair
+BuiltinFunctionChecker::checkOverflow(CheckerContext &C, SVal RetVal,
+  QualType Res) const {
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  ASTContext &ACtx = C.getASTContext();
+
+  // Calling a builtin with a non-integer type result produces compiler error.
+  assert(Res->isIntegerType());
+
+  unsigned BitWidth = ACtx.getIntWidth(Res);
+  auto MinVal =
+  llvm::APSInt::getMinValue(BitWidth, Res->isUnsignedIntegerType());
+  auto MaxVal =
+  llvm::APSInt::getMaxValue(BitWidth, Res->isUnsignedIntegerType());
+
+  SVal IsLeMax =
+  SVB.evalBinOp(State, BO_LE, RetVal, nonloc::ConcreteInt(MaxVal), Res);
+  SVal IsGeMin =
+  SVB.evalBinOp(State, BO_GE, RetVal, nonloc::ConcreteInt(MinVal), Res);
+
+  auto [MayNotOverflow, MayOverflow] =
+  State->assume(IsLeMax.castAs());
+  auto [MayNotUnderflow, MayUnderflow] =
+  State->assume(IsGeMin.castAs());
+
+  return {MayOverflow || MayUnderflow, MayNotOverflow && MayNotUnderflow};
+}
+
+void BuiltinFunctionChecker::handleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // Calling a builtin with an incorrect argument count produces compiler 
error.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetValMax = SVB.evalBinOp(State, Op, Arg1, Arg2,
+ getSufficientTypeForOverflowOp(C, 
ResultType));
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  auto [Overflow, NotOverflow] = checkOverflow(C, RetValMax, ResultType);
+  if (NotOverflow) {
+ProgramStateRef StateNoOverflow =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs()) {
+  StateNoOverflow =
+  StateNoOverflow->bindLoc(*L, RetVal, C.getLocationContext());
+
+  // Propagate taint if any of the argumets were tainted
+  if (isTainted(State, Arg1) || isTainted(State, Arg2))
+StateNoOverflow = addTaint(StateNoOverflow, *L);
+}
+
+C.addTransition(StateNoOverflow);

pskrgag wrote:

Thank you for explanation!

Ok, so based on my local testing, if overflow happens, then result does not end 
up in `InterestingSymbols` in bug reporter, so there is no need to note that 
condition. I tried different tests, but anyway it does not appear in this list.


I ended up just covering non-overflow case in callback.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Donát Nagy via cfe-commits]

@@ -50,6 +118,75 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+std::pair
+BuiltinFunctionChecker::checkOverflow(CheckerContext &C, SVal RetVal,
+  QualType Res) const {
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  ASTContext &ACtx = C.getASTContext();
+
+  // Calling a builtin with a non-integer type result produces compiler error.
+  assert(Res->isIntegerType());
+
+  unsigned BitWidth = ACtx.getIntWidth(Res);
+  auto MinVal =
+  llvm::APSInt::getMinValue(BitWidth, Res->isUnsignedIntegerType());
+  auto MaxVal =
+  llvm::APSInt::getMaxValue(BitWidth, Res->isUnsignedIntegerType());
+
+  SVal IsLeMax =
+  SVB.evalBinOp(State, BO_LE, RetVal, nonloc::ConcreteInt(MaxVal), Res);
+  SVal IsGeMin =
+  SVB.evalBinOp(State, BO_GE, RetVal, nonloc::ConcreteInt(MinVal), Res);
+
+  auto [MayNotOverflow, MayOverflow] =
+  State->assume(IsLeMax.castAs());
+  auto [MayNotUnderflow, MayUnderflow] =
+  State->assume(IsGeMin.castAs());
+
+  return {MayOverflow || MayUnderflow, MayNotOverflow && MayNotUnderflow};
+}
+
+void BuiltinFunctionChecker::handleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // Calling a builtin with an incorrect argument count produces compiler 
error.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetValMax = SVB.evalBinOp(State, Op, Arg1, Arg2,
+ getSufficientTypeForOverflowOp(C, 
ResultType));
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  auto [Overflow, NotOverflow] = checkOverflow(C, RetValMax, ResultType);
+  if (NotOverflow) {
+ProgramStateRef StateNoOverflow =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs()) {
+  StateNoOverflow =
+  StateNoOverflow->bindLoc(*L, RetVal, C.getLocationContext());
+
+  // Propagate taint if any of the argumets were tainted
+  if (isTainted(State, Arg1) || isTainted(State, Arg2))
+StateNoOverflow = addTaint(StateNoOverflow, *L);
+}
+
+C.addTransition(StateNoOverflow);

NagyDonat wrote:

> As far as I see, markInteresting is called on bug reported object. And there 
> is no bug report object, since there is no bug here, we just do assumtions. I 
> tried to find an example in other checkers, but I don't see it.

Yes, that's a good question -- the trick is that when you create a `NoteTag`, 
you can specify a callback that takes a `PathSensitiveBugReport` (by reference) 
and you should use `markInteresting()` within that callback. You could try to 
follow the example of `InvalidPtrChecker::createEnvInvalidationNote()` within 
`InvalidPtrChecker.cpp`, which implements something vaguely similar.

> (Like I see manipulations with markInteresting only during construction of 
> bug report).

When a checker creates a bug report, it can use `markInteresting()` to mark the 
symbols that are _interesting_ (i.e. we used knowledge about them to conclude 
that the situation is buggy).

However, in addition to creating bug reports, checkers can also create 
`NoteTag`s when they do something interesting (e.g. make an assumption, model 
something important etc.) which is not a bug report. There are many trivial 
`NoteTag`s that just print the same plain text message on every bug report that 
passes through the execution step where the `NoteTag` was created, but in 
general the `NoteTag` may have an associated callback which inspects and 
modifies the `PathSensitiveBugReport` (in addition to emitting a "note" 
message).

The idea is that you should create a note tag with a callback which:
- checks whether the return value of the `__builtin_X_overflow()` is 
interesting and returns early if it isn't,
- marks the incoming arguments as interesting (if they're symbolic) to 
propagate interestingness;
- if both cases ("overflow" and "no overflow") were feasible, then returns a 
string message which shows the assumption that was selected.
(This is just a rough draft, there may be intricacies e.g. with describing 
taintedness.)

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

@@ -50,6 +118,75 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+std::pair
+BuiltinFunctionChecker::checkOverflow(CheckerContext &C, SVal RetVal,
+  QualType Res) const {
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  ASTContext &ACtx = C.getASTContext();
+
+  // Calling a builtin with a non-integer type result produces compiler error.
+  assert(Res->isIntegerType());
+
+  unsigned BitWidth = ACtx.getIntWidth(Res);
+  auto MinVal =
+  llvm::APSInt::getMinValue(BitWidth, Res->isUnsignedIntegerType());
+  auto MaxVal =
+  llvm::APSInt::getMaxValue(BitWidth, Res->isUnsignedIntegerType());
+
+  SVal IsLeMax =
+  SVB.evalBinOp(State, BO_LE, RetVal, nonloc::ConcreteInt(MaxVal), Res);
+  SVal IsGeMin =
+  SVB.evalBinOp(State, BO_GE, RetVal, nonloc::ConcreteInt(MinVal), Res);
+
+  auto [MayNotOverflow, MayOverflow] =
+  State->assume(IsLeMax.castAs());
+  auto [MayNotUnderflow, MayUnderflow] =
+  State->assume(IsGeMin.castAs());
+
+  return {MayOverflow || MayUnderflow, MayNotOverflow && MayNotUnderflow};
+}
+
+void BuiltinFunctionChecker::handleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // Calling a builtin with an incorrect argument count produces compiler 
error.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetValMax = SVB.evalBinOp(State, Op, Arg1, Arg2,
+ getSufficientTypeForOverflowOp(C, 
ResultType));
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  auto [Overflow, NotOverflow] = checkOverflow(C, RetValMax, ResultType);
+  if (NotOverflow) {
+ProgramStateRef StateNoOverflow =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs()) {
+  StateNoOverflow =
+  StateNoOverflow->bindLoc(*L, RetVal, C.getLocationContext());
+
+  // Propagate taint if any of the argumets were tainted
+  if (isTainted(State, Arg1) || isTainted(State, Arg2))
+StateNoOverflow = addTaint(StateNoOverflow, *L);
+}
+
+C.addTransition(StateNoOverflow);

pskrgag wrote:

Sorry, I am not sure I get it correctly (I am still learning internals, so 
might be dumb question). 

As far as I see, `markInteresting` is called on bug reported object. And there 
is no bug report object, since there is no bug here, we just do assumtions. I 
tried to find an example in other checkers, but I don't see it.

(Like I see manipulations with `markInteresting` only during construction of 
bug report).

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

@@ -50,6 +118,75 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+std::pair
+BuiltinFunctionChecker::checkOverflow(CheckerContext &C, SVal RetVal,
+  QualType Res) const {
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  ASTContext &ACtx = C.getASTContext();
+
+  // Calling a builtin with a non-integer type result produces compiler error.
+  assert(Res->isIntegerType());
+
+  unsigned BitWidth = ACtx.getIntWidth(Res);
+  auto MinVal =
+  llvm::APSInt::getMinValue(BitWidth, Res->isUnsignedIntegerType());
+  auto MaxVal =
+  llvm::APSInt::getMaxValue(BitWidth, Res->isUnsignedIntegerType());
+
+  SVal IsLeMax =
+  SVB.evalBinOp(State, BO_LE, RetVal, nonloc::ConcreteInt(MaxVal), Res);
+  SVal IsGeMin =
+  SVB.evalBinOp(State, BO_GE, RetVal, nonloc::ConcreteInt(MinVal), Res);
+
+  auto [MayNotOverflow, MayOverflow] =
+  State->assume(IsLeMax.castAs());
+  auto [MayNotUnderflow, MayUnderflow] =
+  State->assume(IsGeMin.castAs());
+
+  return {MayOverflow || MayUnderflow, MayNotOverflow && MayNotUnderflow};
+}
+
+void BuiltinFunctionChecker::handleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // Calling a builtin with an incorrect argument count produces compiler 
error.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetValMax = SVB.evalBinOp(State, Op, Arg1, Arg2,
+ getSufficientTypeForOverflowOp(C, 
ResultType));
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  auto [Overflow, NotOverflow] = checkOverflow(C, RetValMax, ResultType);
+  if (NotOverflow) {
+ProgramStateRef StateNoOverflow =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs()) {
+  StateNoOverflow =
+  StateNoOverflow->bindLoc(*L, RetVal, C.getLocationContext());
+
+  // Propagate taint if any of the argumets were tainted
+  if (isTainted(State, Arg1) || isTainted(State, Arg2))
+StateNoOverflow = addTaint(StateNoOverflow, *L);
+}
+
+C.addTransition(StateNoOverflow);

steakhal wrote:

Yes. To me, here the value is the important thing to track, but that said, we 
are likely more interested in tracking the taint flow, so markInteresting 
should be indeed enough. Thanks.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Donát Nagy via cfe-commits]

@@ -50,6 +118,75 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+std::pair
+BuiltinFunctionChecker::checkOverflow(CheckerContext &C, SVal RetVal,
+  QualType Res) const {
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  ASTContext &ACtx = C.getASTContext();
+
+  // Calling a builtin with a non-integer type result produces compiler error.
+  assert(Res->isIntegerType());
+
+  unsigned BitWidth = ACtx.getIntWidth(Res);
+  auto MinVal =
+  llvm::APSInt::getMinValue(BitWidth, Res->isUnsignedIntegerType());
+  auto MaxVal =
+  llvm::APSInt::getMaxValue(BitWidth, Res->isUnsignedIntegerType());
+
+  SVal IsLeMax =
+  SVB.evalBinOp(State, BO_LE, RetVal, nonloc::ConcreteInt(MaxVal), Res);
+  SVal IsGeMin =
+  SVB.evalBinOp(State, BO_GE, RetVal, nonloc::ConcreteInt(MinVal), Res);
+
+  auto [MayNotOverflow, MayOverflow] =
+  State->assume(IsLeMax.castAs());
+  auto [MayNotUnderflow, MayUnderflow] =
+  State->assume(IsGeMin.castAs());
+
+  return {MayOverflow || MayUnderflow, MayNotOverflow && MayNotUnderflow};
+}
+
+void BuiltinFunctionChecker::handleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // Calling a builtin with an incorrect argument count produces compiler 
error.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetValMax = SVB.evalBinOp(State, Op, Arg1, Arg2,
+ getSufficientTypeForOverflowOp(C, 
ResultType));
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  auto [Overflow, NotOverflow] = checkOverflow(C, RetValMax, ResultType);
+  if (NotOverflow) {
+ProgramStateRef StateNoOverflow =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs()) {
+  StateNoOverflow =
+  StateNoOverflow->bindLoc(*L, RetVal, C.getLocationContext());
+
+  // Propagate taint if any of the argumets were tainted
+  if (isTainted(State, Arg1) || isTainted(State, Arg2))
+StateNoOverflow = addTaint(StateNoOverflow, *L);
+}
+
+C.addTransition(StateNoOverflow);

NagyDonat wrote:

Thanks for the ping, but I think that in this concrete case 
`trackExpressionValue` is probably OK.

I mostly advocated against its use when we were talking about ambitious plans 
that would've required extending the current code and/or using it in new, 
unusual situations. The code of `trackExpressionValue` is ugly and convoluted, 
but it is working (in the sense of "it's working, don't touch it").


By the way, if you want to explain the origin of _symbolic_ values, then 
calling `markInteresting()` on the relevant symbols is another option that may 
be sufficient for your goals. It is less general than `trackExpressionValue()` 
(e.g. it doesn't track concrete values, it doesn't track control dependencies 
etc.) but it doesn't apply random heuristics which are not relevant for you.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

@@ -0,0 +1,157 @@
+// RUN: %clang_analyze_cc1 -triple x86_64-unknown-unknown -verify %s \
+// RUN:   -analyzer-checker=core,debug.ExprInspection
+
+#define __UINT_MAX__ (__INT_MAX__ * 2U + 1U)
+#define __INT_MIN__  (-__INT_MAX__ - 1)
+
+void clang_analyzer_dump_int(int);
+void clang_analyzer_dump_long(long);
+void clang_analyzer_eval(int);
+void clang_analyzer_warnIfReached(void);
+
+void test_add_nooverflow(void)
+{
+   int res;
+
+   if (__builtin_add_overflow(10, 20, &res)) {
+ clang_analyzer_warnIfReached();
+ return;
+   }
+
+   clang_analyzer_dump_int(res); //expected-warning{{30 S32b}}
+}
+
+void test_add_overflow(void)
+{
+   int res;
+
+   if (__builtin_add_overflow(__INT_MAX__, 1, &res)) {
+ clang_analyzer_dump_int(res); //expected-warning{{1st function call 
argument is an uninitialized value}}
+ return;
+   }
+
+   clang_analyzer_warnIfReached();
+}
+
+void test_add_underoverflow(void)
+{
+   int res;
+
+   if (__builtin_add_overflow(__INT_MIN__, -1, &res)) {
+ clang_analyzer_dump_int(res); //expected-warning{{1st function call 
argument is an uninitialized value}}
+ return;
+   }
+
+   clang_analyzer_warnIfReached();
+}
+
+void test_sub_underflow(void)
+{
+   int res;
+
+   if (__builtin_sub_overflow(__INT_MIN__, 10, &res)) {
+ return;
+   }
+
+   clang_analyzer_warnIfReached();
+}
+
+void test_sub_overflow(void)
+{
+   int res;
+
+   if (__builtin_sub_overflow(__INT_MAX__, -1, &res)) {
+ return;
+   }
+
+   clang_analyzer_warnIfReached();
+}
+
+void test_sub_nooverflow(void)
+{
+   int res;
+
+   if (__builtin_sub_overflow(__INT_MAX__, 1, &res)) {
+ clang_analyzer_warnIfReached();
+ return;
+   }
+
+   clang_analyzer_dump_int(res); //expected-warning{{2147483646 S32b}}
+}
+
+void test_mul_overrflow(void)
+{
+   int res;
+
+   if (__builtin_mul_overflow(__INT_MAX__, 2, &res)) {
+ return;
+   }
+
+   clang_analyzer_warnIfReached();
+}
+
+void test_mul_underrflow(void)
+{
+   int res;
+
+   if (__builtin_mul_overflow(__INT_MIN__, -2, &res)) {
+ return;
+   }
+
+   clang_analyzer_warnIfReached();
+}
+
+void test_mul_nooverflow(void)
+{
+   int res;
+
+   if (__builtin_mul_overflow(10, -2, &res)) {
+ clang_analyzer_warnIfReached();
+ return;
+   }
+
+   clang_analyzer_dump_int(res); //expected-warning{{-20 S32b}}
+}
+
+void test_nooverflow_diff_types(void)
+{
+   long res;
+
+   // This is not an overflow, since result type is long.
+   if (__builtin_add_overflow(__INT_MAX__, 1, &res)) {
+ clang_analyzer_warnIfReached();
+ return;
+   }
+
+   clang_analyzer_dump_long(res); //expected-warning{{2147483648 S64b}}
+}
+
+void test_uaddll_overflow_contraints(unsigned long a, unsigned long b)
+{
+   unsigned long long res;
+
+   if (a != 10)
+ return;
+   if (b != 10)

pskrgag wrote:

I've tried to add smth like this, but it fails even for more simple constraint 
like `if (a > 10 || b > 10) return`; for unsigned case. See 
https://github.com/llvm/llvm-project/pull/102602#discussion_r1712211946.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

@@ -0,0 +1,157 @@
+// RUN: %clang_analyze_cc1 -triple x86_64-unknown-unknown -verify %s \
+// RUN:   -analyzer-checker=core,debug.ExprInspection
+
+#define __UINT_MAX__ (__INT_MAX__ * 2U + 1U)
+#define __INT_MIN__  (-__INT_MAX__ - 1)
+
+void clang_analyzer_dump_int(int);
+void clang_analyzer_dump_long(long);
+void clang_analyzer_eval(int);
+void clang_analyzer_warnIfReached(void);
+
+void test_add_nooverflow(void)
+{
+   int res;
+
+   if (__builtin_add_overflow(10, 20, &res)) {
+ clang_analyzer_warnIfReached();
+ return;
+   }
+
+   clang_analyzer_dump_int(res); //expected-warning{{30 S32b}}
+}
+
+void test_add_overflow(void)
+{
+   int res;
+
+   if (__builtin_add_overflow(__INT_MAX__, 1, &res)) {
+ clang_analyzer_dump_int(res); //expected-warning{{1st function call 
argument is an uninitialized value}}
+ return;
+   }
+
+   clang_analyzer_warnIfReached();
+}
+
+void test_add_underoverflow(void)
+{
+   int res;
+
+   if (__builtin_add_overflow(__INT_MIN__, -1, &res)) {
+ clang_analyzer_dump_int(res); //expected-warning{{1st function call 
argument is an uninitialized value}}
+ return;
+   }
+
+   clang_analyzer_warnIfReached();
+}
+
+void test_sub_underflow(void)
+{
+   int res;
+
+   if (__builtin_sub_overflow(__INT_MIN__, 10, &res)) {
+ return;
+   }
+
+   clang_analyzer_warnIfReached();
+}
+
+void test_sub_overflow(void)
+{
+   int res;
+
+   if (__builtin_sub_overflow(__INT_MAX__, -1, &res)) {
+ return;
+   }
+
+   clang_analyzer_warnIfReached();
+}
+
+void test_sub_nooverflow(void)
+{
+   int res;
+
+   if (__builtin_sub_overflow(__INT_MAX__, 1, &res)) {
+ clang_analyzer_warnIfReached();
+ return;
+   }
+
+   clang_analyzer_dump_int(res); //expected-warning{{2147483646 S32b}}
+}
+
+void test_mul_overrflow(void)
+{
+   int res;
+
+   if (__builtin_mul_overflow(__INT_MAX__, 2, &res)) {
+ return;
+   }
+
+   clang_analyzer_warnIfReached();
+}
+
+void test_mul_underrflow(void)
+{
+   int res;
+
+   if (__builtin_mul_overflow(__INT_MIN__, -2, &res)) {
+ return;
+   }
+
+   clang_analyzer_warnIfReached();
+}
+
+void test_mul_nooverflow(void)
+{
+   int res;
+
+   if (__builtin_mul_overflow(10, -2, &res)) {
+ clang_analyzer_warnIfReached();
+ return;
+   }
+
+   clang_analyzer_dump_int(res); //expected-warning{{-20 S32b}}
+}
+
+void test_nooverflow_diff_types(void)
+{
+   long res;
+
+   // This is not an overflow, since result type is long.
+   if (__builtin_add_overflow(__INT_MAX__, 1, &res)) {
+ clang_analyzer_warnIfReached();
+ return;
+   }
+
+   clang_analyzer_dump_long(res); //expected-warning{{2147483648 S64b}}
+}
+
+void test_uaddll_overflow_contraints(unsigned long a, unsigned long b)
+{
+   unsigned long long res;
+
+   if (a != 10)
+ return;
+   if (b != 10)

steakhal wrote:

Such constraints we call "perfect constraints" as they narrow down the value 
domain to a single value. After this, the engine will fold all uses of this 
into a concreteInt, eliminating the symbolic value.

Consequently, perfect constraints are different to common constraints. They 
should have separate tests.

That said, two symbolic values with half side constraints are missing. x>=(int 
max -2, y>= 10 for instance.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

https://github.com/steakhal edited 
https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

@@ -50,6 +118,75 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+std::pair
+BuiltinFunctionChecker::checkOverflow(CheckerContext &C, SVal RetVal,
+  QualType Res) const {
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  ASTContext &ACtx = C.getASTContext();
+
+  // Calling a builtin with a non-integer type result produces compiler error.
+  assert(Res->isIntegerType());
+
+  unsigned BitWidth = ACtx.getIntWidth(Res);
+  auto MinVal =
+  llvm::APSInt::getMinValue(BitWidth, Res->isUnsignedIntegerType());
+  auto MaxVal =
+  llvm::APSInt::getMaxValue(BitWidth, Res->isUnsignedIntegerType());
+
+  SVal IsLeMax =
+  SVB.evalBinOp(State, BO_LE, RetVal, nonloc::ConcreteInt(MaxVal), Res);
+  SVal IsGeMin =
+  SVB.evalBinOp(State, BO_GE, RetVal, nonloc::ConcreteInt(MinVal), Res);
+
+  auto [MayNotOverflow, MayOverflow] =
+  State->assume(IsLeMax.castAs());
+  auto [MayNotUnderflow, MayUnderflow] =
+  State->assume(IsGeMin.castAs());
+
+  return {MayOverflow || MayUnderflow, MayNotOverflow && MayNotUnderflow};
+}
+
+void BuiltinFunctionChecker::handleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // Calling a builtin with an incorrect argument count produces compiler 
error.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetValMax = SVB.evalBinOp(State, Op, Arg1, Arg2,
+ getSufficientTypeForOverflowOp(C, 
ResultType));
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  auto [Overflow, NotOverflow] = checkOverflow(C, RetValMax, ResultType);
+  if (NotOverflow) {
+ProgramStateRef StateNoOverflow =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs()) {
+  StateNoOverflow =
+  StateNoOverflow->bindLoc(*L, RetVal, C.getLocationContext());
+
+  // Propagate taint if any of the argumets were tainted
+  if (isTainted(State, Arg1) || isTainted(State, Arg2))
+StateNoOverflow = addTaint(StateNoOverflow, *L);
+}
+
+C.addTransition(StateNoOverflow);

steakhal wrote:

This transition should add a NoteTag highlighting that we assumed to have no 
overflow iff the StateOverflow was also valid. In that case, it should probably 
also call trackExpressionValue on both or some of the operands that played a 
role in that decision.
@NagyDonat is usually against trackExprVal, so I'm tagging him.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

https://github.com/steakhal commented:

Looks really good. I only had some notes w.r.t. note tags.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

pskrgag wrote:

gentle ping

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

pskrgag wrote:

Oh, sorry for ping then. PR is not urgent at all.

Have a fun vacation! =)

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

steakhal wrote:

I'm on vacation for some time now.
Maybe others can chim in. Should I ping someone?

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

pskrgag wrote:

Could you, please, check the lattest vestion, if you have time? 

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

https://github.com/pskrgag updated 
https://github.com/llvm/llvm-project/pull/102602

>From 7b4f999b39f4308cab253204e6be41ea7a70f695 Mon Sep 17 00:00:00 2001
From: Pavel Skripkin 
Date: Fri, 9 Aug 2024 14:37:47 +0300
Subject: [PATCH 1/7] clang/csa: add initial support for builtin overflow

---
 .../Checkers/BuiltinFunctionChecker.cpp   | 124 +-
 clang/test/Analysis/builtin_overflow.c|  65 +
 .../test/Analysis/out-of-bounds-diagnostics.c |  17 +++
 3 files changed, 204 insertions(+), 2 deletions(-)
 create mode 100644 clang/test/Analysis/builtin_overflow.c

diff --git a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp 
b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
index b198b1c2ff4d11..0c8b9fa3d947b0 100644
--- a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
+++ b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
@@ -21,16 +21,67 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 
+QualType getOverflowBuiltinResultType(const CallEvent &Call) {
+  assert(Call.getNumArgs() == 3);
+
+  return Call.getArgExpr(2)->getType()->getPointeeType();
+}
+
+QualType getOverflowBuiltinResultType(const CallEvent &Call, CheckerContext &C,
+  unsigned BI) {
+  assert(Call.getNumArgs() == 3);
+
+  ASTContext &Ast = C.getASTContext();
+
+  switch (BI) {
+  case Builtin::BI__builtin_smul_overflow:
+  case Builtin::BI__builtin_ssub_overflow:
+  case Builtin::BI__builtin_sadd_overflow:
+return Ast.IntTy;
+  case Builtin::BI__builtin_smull_overflow:
+  case Builtin::BI__builtin_ssubl_overflow:
+  case Builtin::BI__builtin_saddl_overflow:
+return Ast.LongTy;
+  case Builtin::BI__builtin_smulll_overflow:
+  case Builtin::BI__builtin_ssubll_overflow:
+  case Builtin::BI__builtin_saddll_overflow:
+return Ast.LongLongTy;
+  case Builtin::BI__builtin_umul_overflow:
+  case Builtin::BI__builtin_usub_overflow:
+  case Builtin::BI__builtin_uadd_overflow:
+return Ast.UnsignedIntTy;
+  case Builtin::BI__builtin_umull_overflow:
+  case Builtin::BI__builtin_usubl_overflow:
+  case Builtin::BI__builtin_uaddl_overflow:
+return Ast.UnsignedLongTy;
+  case Builtin::BI__builtin_umulll_overflow:
+  case Builtin::BI__builtin_usubll_overflow:
+  case Builtin::BI__builtin_uaddll_overflow:
+return Ast.UnsignedLongLongTy;
+  case Builtin::BI__builtin_mul_overflow:
+  case Builtin::BI__builtin_sub_overflow:
+  case Builtin::BI__builtin_add_overflow:
+return getOverflowBuiltinResultType(Call);
+  default:
+assert(false && "Unknown overflow builtin");
+  }
+}
+
 class BuiltinFunctionChecker : public Checker {
 public:
   bool evalCall(const CallEvent &Call, CheckerContext &C) const;
+  void HandleOverflowBuiltin(const CallEvent &Call, CheckerContext &C,
+ BinaryOperator::Opcode Op,
+ QualType ResultType) const;
 
 private:
   // From: clang/include/clang/Basic/Builtins.def
@@ -50,6 +101,44 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+void BuiltinFunctionChecker::HandleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // All __builtin_*_overflow functions take 3 argumets.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  // TODO: Handle overflows with values that known to overflow. Like INT_MAX + 
1
+  // should not produce state for non-overflow case and threat it as
+  // unreachable.
+
+  // Handle non-overflow case.
+  {
+ProgramStateRef StateSuccess =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs())
+  StateSuccess = StateSuccess->bindLoc(*L, RetVal, C.getLocationContext());
+
+C.addTransition(StateSuccess);
+  }
+
+  // Handle overflow case.
+  {
+C.addTransition(
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(true)));
+  }
+}
+
 bool BuiltinFunctionChecker::isBuiltinLikeFunction(
 const CallEvent &Call) const {
   const auto *FD = llvm::dyn_cast_or_null(Call.getDecl());
@@ -82,10 +171,41 @@ bool BuiltinFunctionChe

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

pskrgag wrote:

> Try using the Github merge workflow to avoid doing force-pushes. Those are 
> destructive for inline comments done for the PR. On force-push, GH can't 
> follow to which line it should migrate the existing inline comments, thus 
> drops them.
> 

Sorry again for fp =(. I am getting used to rebase+fp workflow, since I've 
never worked with gh flow. I am trying to switch my brain while developing 
llvm, but sometimes I mess up.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

steakhal wrote:

Try using the Github merge workflow to avoid doing force-pushes. Those are 
destructive for inline comments done for the PR. On force-push, GH can't follow 
to which line it should migrate the existing inline comments, thus drops them.

You should just do a fetch main, merge main, push branch (without force).

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Donát Nagy via cfe-commits]

https://github.com/NagyDonat edited 
https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Donát Nagy via cfe-commits]

https://github.com/NagyDonat edited 
https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Donát Nagy via cfe-commits]

@@ -50,6 +101,44 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+void BuiltinFunctionChecker::HandleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // All __builtin_*_overflow functions take 3 argumets.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  // TODO: Handle overflows with values that known to overflow. Like INT_MAX + 
1
+  // should not produce state for non-overflow case and threat it as

NagyDonat wrote:

I did some digging in `RangedConstraintManager` and it seems that algebraic 
expressions that involve two symbolic values **are handled as black boxes** by 
the analyzer: in your example it creates a `SymSymExpr` that is known to be the 
sum of `a` and `b`, but we don't have any logic which would constrain the 
potential values of this `SymSymExpr` based on the constraints known about the 
operands. (The analyzer can propagate information in the easier case when it 
knows the exact value of one of the operands.)

I don't know why do we have this shameful limitation... I'd guess that 
implementing the necessary `RangeSet` operation wouldn't be prohibitively 
difficult, but there may be performance implications, and perhaps 
well-constrained (but not exactly known) values are not common enough to make 
this a valuable investment.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

@@ -50,6 +101,44 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+void BuiltinFunctionChecker::HandleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // All __builtin_*_overflow functions take 3 argumets.
+  assert(Call.getNumArgs() == 3);

pskrgag wrote:

Added comments to the asserts (about number of arguments and result type) and 
added taint propagation

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

https://github.com/pskrgag updated 
https://github.com/llvm/llvm-project/pull/102602

>From 7b4f999b39f4308cab253204e6be41ea7a70f695 Mon Sep 17 00:00:00 2001
From: Pavel Skripkin 
Date: Fri, 9 Aug 2024 14:37:47 +0300
Subject: [PATCH 1/6] clang/csa: add initial support for builtin overflow

---
 .../Checkers/BuiltinFunctionChecker.cpp   | 124 +-
 clang/test/Analysis/builtin_overflow.c|  65 +
 .../test/Analysis/out-of-bounds-diagnostics.c |  17 +++
 3 files changed, 204 insertions(+), 2 deletions(-)
 create mode 100644 clang/test/Analysis/builtin_overflow.c

diff --git a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp 
b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
index b198b1c2ff4d11..0c8b9fa3d947b0 100644
--- a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
+++ b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
@@ -21,16 +21,67 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 
+QualType getOverflowBuiltinResultType(const CallEvent &Call) {
+  assert(Call.getNumArgs() == 3);
+
+  return Call.getArgExpr(2)->getType()->getPointeeType();
+}
+
+QualType getOverflowBuiltinResultType(const CallEvent &Call, CheckerContext &C,
+  unsigned BI) {
+  assert(Call.getNumArgs() == 3);
+
+  ASTContext &Ast = C.getASTContext();
+
+  switch (BI) {
+  case Builtin::BI__builtin_smul_overflow:
+  case Builtin::BI__builtin_ssub_overflow:
+  case Builtin::BI__builtin_sadd_overflow:
+return Ast.IntTy;
+  case Builtin::BI__builtin_smull_overflow:
+  case Builtin::BI__builtin_ssubl_overflow:
+  case Builtin::BI__builtin_saddl_overflow:
+return Ast.LongTy;
+  case Builtin::BI__builtin_smulll_overflow:
+  case Builtin::BI__builtin_ssubll_overflow:
+  case Builtin::BI__builtin_saddll_overflow:
+return Ast.LongLongTy;
+  case Builtin::BI__builtin_umul_overflow:
+  case Builtin::BI__builtin_usub_overflow:
+  case Builtin::BI__builtin_uadd_overflow:
+return Ast.UnsignedIntTy;
+  case Builtin::BI__builtin_umull_overflow:
+  case Builtin::BI__builtin_usubl_overflow:
+  case Builtin::BI__builtin_uaddl_overflow:
+return Ast.UnsignedLongTy;
+  case Builtin::BI__builtin_umulll_overflow:
+  case Builtin::BI__builtin_usubll_overflow:
+  case Builtin::BI__builtin_uaddll_overflow:
+return Ast.UnsignedLongLongTy;
+  case Builtin::BI__builtin_mul_overflow:
+  case Builtin::BI__builtin_sub_overflow:
+  case Builtin::BI__builtin_add_overflow:
+return getOverflowBuiltinResultType(Call);
+  default:
+assert(false && "Unknown overflow builtin");
+  }
+}
+
 class BuiltinFunctionChecker : public Checker {
 public:
   bool evalCall(const CallEvent &Call, CheckerContext &C) const;
+  void HandleOverflowBuiltin(const CallEvent &Call, CheckerContext &C,
+ BinaryOperator::Opcode Op,
+ QualType ResultType) const;
 
 private:
   // From: clang/include/clang/Basic/Builtins.def
@@ -50,6 +101,44 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+void BuiltinFunctionChecker::HandleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // All __builtin_*_overflow functions take 3 argumets.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  // TODO: Handle overflows with values that known to overflow. Like INT_MAX + 
1
+  // should not produce state for non-overflow case and threat it as
+  // unreachable.
+
+  // Handle non-overflow case.
+  {
+ProgramStateRef StateSuccess =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs())
+  StateSuccess = StateSuccess->bindLoc(*L, RetVal, C.getLocationContext());
+
+C.addTransition(StateSuccess);
+  }
+
+  // Handle overflow case.
+  {
+C.addTransition(
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(true)));
+  }
+}
+
 bool BuiltinFunctionChecker::isBuiltinLikeFunction(
 const CallEvent &Call) const {
   const auto *FD = llvm::dyn_cast_or_null(Call.getDecl());
@@ -82,10 +171,41 @@ bool BuiltinFunctionChe

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

@@ -50,6 +101,44 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+void BuiltinFunctionChecker::HandleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // All __builtin_*_overflow functions take 3 argumets.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  // TODO: Handle overflows with values that known to overflow. Like INT_MAX + 
1
+  // should not produce state for non-overflow case and threat it as

pskrgag wrote:

> Assuming that a and b are signed integers

Oh, sorry, I forgot to mention that `a` and `b` are unsigned. I've showed this 
in `test_uadd_overflow_contraints` test in this pr

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Donát Nagy via cfe-commits]

https://github.com/NagyDonat edited 
https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Donát Nagy via cfe-commits]

@@ -50,6 +101,44 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+void BuiltinFunctionChecker::HandleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // All __builtin_*_overflow functions take 3 argumets.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  // TODO: Handle overflows with values that known to overflow. Like INT_MAX + 
1
+  // should not produce state for non-overflow case and threat it as

NagyDonat wrote:

> `clang_analyzer_eval(a + b < 30); <--- Prints 1 and 0, but why ???`

Assuming that `a` and `b` are signed integers, they can be very negative, and 
then their sum can be a positive value above 30 (after an overflow). This means 
that both boolean values are possible for the expression `a + b < 30`, and the 
analyzer represents this by printing both 1 and 0.

(If I understand this correctly, we get two definite numbers instead of one 
range because the on-by-default `eagerlyAssume` mode causes a state split when 
it sees the comparison operator in `a + b < 30`, despite the fact that this is 
not in a conditional expression.)




https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

https://github.com/pskrgag updated 
https://github.com/llvm/llvm-project/pull/102602

>From 7b4f999b39f4308cab253204e6be41ea7a70f695 Mon Sep 17 00:00:00 2001
From: Pavel Skripkin 
Date: Fri, 9 Aug 2024 14:37:47 +0300
Subject: [PATCH 1/5] clang/csa: add initial support for builtin overflow

---
 .../Checkers/BuiltinFunctionChecker.cpp   | 124 +-
 clang/test/Analysis/builtin_overflow.c|  65 +
 .../test/Analysis/out-of-bounds-diagnostics.c |  17 +++
 3 files changed, 204 insertions(+), 2 deletions(-)
 create mode 100644 clang/test/Analysis/builtin_overflow.c

diff --git a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp 
b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
index b198b1c2ff4d11..0c8b9fa3d947b0 100644
--- a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
+++ b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
@@ -21,16 +21,67 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 
+QualType getOverflowBuiltinResultType(const CallEvent &Call) {
+  assert(Call.getNumArgs() == 3);
+
+  return Call.getArgExpr(2)->getType()->getPointeeType();
+}
+
+QualType getOverflowBuiltinResultType(const CallEvent &Call, CheckerContext &C,
+  unsigned BI) {
+  assert(Call.getNumArgs() == 3);
+
+  ASTContext &Ast = C.getASTContext();
+
+  switch (BI) {
+  case Builtin::BI__builtin_smul_overflow:
+  case Builtin::BI__builtin_ssub_overflow:
+  case Builtin::BI__builtin_sadd_overflow:
+return Ast.IntTy;
+  case Builtin::BI__builtin_smull_overflow:
+  case Builtin::BI__builtin_ssubl_overflow:
+  case Builtin::BI__builtin_saddl_overflow:
+return Ast.LongTy;
+  case Builtin::BI__builtin_smulll_overflow:
+  case Builtin::BI__builtin_ssubll_overflow:
+  case Builtin::BI__builtin_saddll_overflow:
+return Ast.LongLongTy;
+  case Builtin::BI__builtin_umul_overflow:
+  case Builtin::BI__builtin_usub_overflow:
+  case Builtin::BI__builtin_uadd_overflow:
+return Ast.UnsignedIntTy;
+  case Builtin::BI__builtin_umull_overflow:
+  case Builtin::BI__builtin_usubl_overflow:
+  case Builtin::BI__builtin_uaddl_overflow:
+return Ast.UnsignedLongTy;
+  case Builtin::BI__builtin_umulll_overflow:
+  case Builtin::BI__builtin_usubll_overflow:
+  case Builtin::BI__builtin_uaddll_overflow:
+return Ast.UnsignedLongLongTy;
+  case Builtin::BI__builtin_mul_overflow:
+  case Builtin::BI__builtin_sub_overflow:
+  case Builtin::BI__builtin_add_overflow:
+return getOverflowBuiltinResultType(Call);
+  default:
+assert(false && "Unknown overflow builtin");
+  }
+}
+
 class BuiltinFunctionChecker : public Checker {
 public:
   bool evalCall(const CallEvent &Call, CheckerContext &C) const;
+  void HandleOverflowBuiltin(const CallEvent &Call, CheckerContext &C,
+ BinaryOperator::Opcode Op,
+ QualType ResultType) const;
 
 private:
   // From: clang/include/clang/Basic/Builtins.def
@@ -50,6 +101,44 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+void BuiltinFunctionChecker::HandleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // All __builtin_*_overflow functions take 3 argumets.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  // TODO: Handle overflows with values that known to overflow. Like INT_MAX + 
1
+  // should not produce state for non-overflow case and threat it as
+  // unreachable.
+
+  // Handle non-overflow case.
+  {
+ProgramStateRef StateSuccess =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs())
+  StateSuccess = StateSuccess->bindLoc(*L, RetVal, C.getLocationContext());
+
+C.addTransition(StateSuccess);
+  }
+
+  // Handle overflow case.
+  {
+C.addTransition(
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(true)));
+  }
+}
+
 bool BuiltinFunctionChecker::isBuiltinLikeFunction(
 const CallEvent &Call) const {
   const auto *FD = llvm::dyn_cast_or_null(Call.getDecl());
@@ -82,10 +171,41 @@ bool BuiltinFunctionChe

[clang] [analyzer] Model overflow builtins (PR #102602)

[Donát Nagy via cfe-commits]

https://github.com/NagyDonat edited 
https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Donát Nagy via cfe-commits]

@@ -50,6 +101,44 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+void BuiltinFunctionChecker::HandleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // All __builtin_*_overflow functions take 3 argumets.
+  assert(Call.getNumArgs() == 3);

NagyDonat wrote:

> I've tried to catch this assert locally by calling __builtin_*_overflow with 
> 2 arguments, but clang just rejects it.

Oh, I see. Perhaps add a comment saying that "Calling a builtin with an 
incorrect argument count produces compiler error (...)", because e.g. I didn't 
know that this is the case.

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

https://github.com/pskrgag updated 
https://github.com/llvm/llvm-project/pull/102602

>From 7b4f999b39f4308cab253204e6be41ea7a70f695 Mon Sep 17 00:00:00 2001
From: Pavel Skripkin 
Date: Fri, 9 Aug 2024 14:37:47 +0300
Subject: [PATCH 1/4] clang/csa: add initial support for builtin overflow

---
 .../Checkers/BuiltinFunctionChecker.cpp   | 124 +-
 clang/test/Analysis/builtin_overflow.c|  65 +
 .../test/Analysis/out-of-bounds-diagnostics.c |  17 +++
 3 files changed, 204 insertions(+), 2 deletions(-)
 create mode 100644 clang/test/Analysis/builtin_overflow.c

diff --git a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp 
b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
index b198b1c2ff4d11..0c8b9fa3d947b0 100644
--- a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
+++ b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
@@ -21,16 +21,67 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 
+QualType getOverflowBuiltinResultType(const CallEvent &Call) {
+  assert(Call.getNumArgs() == 3);
+
+  return Call.getArgExpr(2)->getType()->getPointeeType();
+}
+
+QualType getOverflowBuiltinResultType(const CallEvent &Call, CheckerContext &C,
+  unsigned BI) {
+  assert(Call.getNumArgs() == 3);
+
+  ASTContext &Ast = C.getASTContext();
+
+  switch (BI) {
+  case Builtin::BI__builtin_smul_overflow:
+  case Builtin::BI__builtin_ssub_overflow:
+  case Builtin::BI__builtin_sadd_overflow:
+return Ast.IntTy;
+  case Builtin::BI__builtin_smull_overflow:
+  case Builtin::BI__builtin_ssubl_overflow:
+  case Builtin::BI__builtin_saddl_overflow:
+return Ast.LongTy;
+  case Builtin::BI__builtin_smulll_overflow:
+  case Builtin::BI__builtin_ssubll_overflow:
+  case Builtin::BI__builtin_saddll_overflow:
+return Ast.LongLongTy;
+  case Builtin::BI__builtin_umul_overflow:
+  case Builtin::BI__builtin_usub_overflow:
+  case Builtin::BI__builtin_uadd_overflow:
+return Ast.UnsignedIntTy;
+  case Builtin::BI__builtin_umull_overflow:
+  case Builtin::BI__builtin_usubl_overflow:
+  case Builtin::BI__builtin_uaddl_overflow:
+return Ast.UnsignedLongTy;
+  case Builtin::BI__builtin_umulll_overflow:
+  case Builtin::BI__builtin_usubll_overflow:
+  case Builtin::BI__builtin_uaddll_overflow:
+return Ast.UnsignedLongLongTy;
+  case Builtin::BI__builtin_mul_overflow:
+  case Builtin::BI__builtin_sub_overflow:
+  case Builtin::BI__builtin_add_overflow:
+return getOverflowBuiltinResultType(Call);
+  default:
+assert(false && "Unknown overflow builtin");
+  }
+}
+
 class BuiltinFunctionChecker : public Checker {
 public:
   bool evalCall(const CallEvent &Call, CheckerContext &C) const;
+  void HandleOverflowBuiltin(const CallEvent &Call, CheckerContext &C,
+ BinaryOperator::Opcode Op,
+ QualType ResultType) const;
 
 private:
   // From: clang/include/clang/Basic/Builtins.def
@@ -50,6 +101,44 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+void BuiltinFunctionChecker::HandleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // All __builtin_*_overflow functions take 3 argumets.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  // TODO: Handle overflows with values that known to overflow. Like INT_MAX + 
1
+  // should not produce state for non-overflow case and threat it as
+  // unreachable.
+
+  // Handle non-overflow case.
+  {
+ProgramStateRef StateSuccess =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs())
+  StateSuccess = StateSuccess->bindLoc(*L, RetVal, C.getLocationContext());
+
+C.addTransition(StateSuccess);
+  }
+
+  // Handle overflow case.
+  {
+C.addTransition(
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(true)));
+  }
+}
+
 bool BuiltinFunctionChecker::isBuiltinLikeFunction(
 const CallEvent &Call) const {
   const auto *FD = llvm::dyn_cast_or_null(Call.getDecl());
@@ -82,10 +171,41 @@ bool BuiltinFunctionChe

[clang] [analyzer] Model overflow builtins (PR #102602)

[via cfe-commits]

github-actions[bot] wrote:




:warning: C/C++ code formatter, clang-format found issues in your code. 
:warning:



You can test this locally with the following command:


``bash
git-clang-format --diff 3364284d87035eaac9662d345d4ddee2714f8fd7 
a928600fcf613ff1f85fa1e5093c7973d4b8cfb8 --extensions cpp,c -- 
clang/test/Analysis/builtin_overflow.c 
clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp 
clang/test/Analysis/out-of-bounds-diagnostics.c
``





View the diff from clang-format here.


``diff
diff --git a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp 
b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
index 5d7760c131..1507973c63 100644
--- a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
+++ b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
@@ -122,14 +122,20 @@ BuiltinFunctionChecker::checkOverflow(CheckerContext &C, 
SVal RetVal,
   assert(Res->isIntegerType());
 
   unsigned BitWidth = ACtx.getIntWidth(Res);
-  auto MinVal = llvm::APSInt::getMinValue(BitWidth, 
Res->isUnsignedIntegerType());
-  auto MaxVal = llvm::APSInt::getMaxValue(BitWidth, 
Res->isUnsignedIntegerType());
-
-  SVal IsLeMax = SVB.evalBinOp(State, BO_LE, RetVal, 
nonloc::ConcreteInt(MaxVal), Res);
-  SVal IsGeMin = SVB.evalBinOp(State, BO_GE, RetVal, 
nonloc::ConcreteInt(MinVal), Res);
-
-  auto [MayNotOverflow, MayOverflow] = 
State->assume(IsLeMax.castAs());
-  auto [MayNotUnderflow, MayUnderflow] = 
State->assume(IsGeMin.castAs());
+  auto MinVal =
+  llvm::APSInt::getMinValue(BitWidth, Res->isUnsignedIntegerType());
+  auto MaxVal =
+  llvm::APSInt::getMaxValue(BitWidth, Res->isUnsignedIntegerType());
+
+  SVal IsLeMax =
+  SVB.evalBinOp(State, BO_LE, RetVal, nonloc::ConcreteInt(MaxVal), Res);
+  SVal IsGeMin =
+  SVB.evalBinOp(State, BO_GE, RetVal, nonloc::ConcreteInt(MinVal), Res);
+
+  auto [MayNotOverflow, MayOverflow] =
+  State->assume(IsLeMax.castAs());
+  auto [MayNotUnderflow, MayUnderflow] =
+  State->assume(IsGeMin.castAs());
 
   return {MayOverflow || MayUnderflow, MayNotOverflow && MayNotUnderflow};
 }

``




https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

https://github.com/pskrgag updated 
https://github.com/llvm/llvm-project/pull/102602

>From 3e0fcffa8fbea5f89ab927fd897c451bcafd8e5e Mon Sep 17 00:00:00 2001
From: Pavel Skripkin 
Date: Fri, 9 Aug 2024 14:37:47 +0300
Subject: [PATCH 1/4] clang/csa: add initial support for builtin overflow

---
 .../Checkers/BuiltinFunctionChecker.cpp   | 124 +-
 clang/test/Analysis/builtin_overflow.c|  65 +
 .../test/Analysis/out-of-bounds-diagnostics.c |  17 +++
 3 files changed, 204 insertions(+), 2 deletions(-)
 create mode 100644 clang/test/Analysis/builtin_overflow.c

diff --git a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp 
b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
index b198b1c2ff4d11..0c8b9fa3d947b0 100644
--- a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
+++ b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
@@ -21,16 +21,67 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 
+QualType getOverflowBuiltinResultType(const CallEvent &Call) {
+  assert(Call.getNumArgs() == 3);
+
+  return Call.getArgExpr(2)->getType()->getPointeeType();
+}
+
+QualType getOverflowBuiltinResultType(const CallEvent &Call, CheckerContext &C,
+  unsigned BI) {
+  assert(Call.getNumArgs() == 3);
+
+  ASTContext &Ast = C.getASTContext();
+
+  switch (BI) {
+  case Builtin::BI__builtin_smul_overflow:
+  case Builtin::BI__builtin_ssub_overflow:
+  case Builtin::BI__builtin_sadd_overflow:
+return Ast.IntTy;
+  case Builtin::BI__builtin_smull_overflow:
+  case Builtin::BI__builtin_ssubl_overflow:
+  case Builtin::BI__builtin_saddl_overflow:
+return Ast.LongTy;
+  case Builtin::BI__builtin_smulll_overflow:
+  case Builtin::BI__builtin_ssubll_overflow:
+  case Builtin::BI__builtin_saddll_overflow:
+return Ast.LongLongTy;
+  case Builtin::BI__builtin_umul_overflow:
+  case Builtin::BI__builtin_usub_overflow:
+  case Builtin::BI__builtin_uadd_overflow:
+return Ast.UnsignedIntTy;
+  case Builtin::BI__builtin_umull_overflow:
+  case Builtin::BI__builtin_usubl_overflow:
+  case Builtin::BI__builtin_uaddl_overflow:
+return Ast.UnsignedLongTy;
+  case Builtin::BI__builtin_umulll_overflow:
+  case Builtin::BI__builtin_usubll_overflow:
+  case Builtin::BI__builtin_uaddll_overflow:
+return Ast.UnsignedLongLongTy;
+  case Builtin::BI__builtin_mul_overflow:
+  case Builtin::BI__builtin_sub_overflow:
+  case Builtin::BI__builtin_add_overflow:
+return getOverflowBuiltinResultType(Call);
+  default:
+assert(false && "Unknown overflow builtin");
+  }
+}
+
 class BuiltinFunctionChecker : public Checker {
 public:
   bool evalCall(const CallEvent &Call, CheckerContext &C) const;
+  void HandleOverflowBuiltin(const CallEvent &Call, CheckerContext &C,
+ BinaryOperator::Opcode Op,
+ QualType ResultType) const;
 
 private:
   // From: clang/include/clang/Basic/Builtins.def
@@ -50,6 +101,44 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+void BuiltinFunctionChecker::HandleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // All __builtin_*_overflow functions take 3 argumets.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  // TODO: Handle overflows with values that known to overflow. Like INT_MAX + 
1
+  // should not produce state for non-overflow case and threat it as
+  // unreachable.
+
+  // Handle non-overflow case.
+  {
+ProgramStateRef StateSuccess =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs())
+  StateSuccess = StateSuccess->bindLoc(*L, RetVal, C.getLocationContext());
+
+C.addTransition(StateSuccess);
+  }
+
+  // Handle overflow case.
+  {
+C.addTransition(
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(true)));
+  }
+}
+
 bool BuiltinFunctionChecker::isBuiltinLikeFunction(
 const CallEvent &Call) const {
   const auto *FD = llvm::dyn_cast_or_null(Call.getDecl());
@@ -82,10 +171,41 @@ bool BuiltinFunctionChe

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

https://github.com/pskrgag updated 
https://github.com/llvm/llvm-project/pull/102602

>From 3e0fcffa8fbea5f89ab927fd897c451bcafd8e5e Mon Sep 17 00:00:00 2001
From: Pavel Skripkin 
Date: Fri, 9 Aug 2024 14:37:47 +0300
Subject: [PATCH 1/3] clang/csa: add initial support for builtin overflow

---
 .../Checkers/BuiltinFunctionChecker.cpp   | 124 +-
 clang/test/Analysis/builtin_overflow.c|  65 +
 .../test/Analysis/out-of-bounds-diagnostics.c |  17 +++
 3 files changed, 204 insertions(+), 2 deletions(-)
 create mode 100644 clang/test/Analysis/builtin_overflow.c

diff --git a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp 
b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
index b198b1c2ff4d11..0c8b9fa3d947b0 100644
--- a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
+++ b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
@@ -21,16 +21,67 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 
+QualType getOverflowBuiltinResultType(const CallEvent &Call) {
+  assert(Call.getNumArgs() == 3);
+
+  return Call.getArgExpr(2)->getType()->getPointeeType();
+}
+
+QualType getOverflowBuiltinResultType(const CallEvent &Call, CheckerContext &C,
+  unsigned BI) {
+  assert(Call.getNumArgs() == 3);
+
+  ASTContext &Ast = C.getASTContext();
+
+  switch (BI) {
+  case Builtin::BI__builtin_smul_overflow:
+  case Builtin::BI__builtin_ssub_overflow:
+  case Builtin::BI__builtin_sadd_overflow:
+return Ast.IntTy;
+  case Builtin::BI__builtin_smull_overflow:
+  case Builtin::BI__builtin_ssubl_overflow:
+  case Builtin::BI__builtin_saddl_overflow:
+return Ast.LongTy;
+  case Builtin::BI__builtin_smulll_overflow:
+  case Builtin::BI__builtin_ssubll_overflow:
+  case Builtin::BI__builtin_saddll_overflow:
+return Ast.LongLongTy;
+  case Builtin::BI__builtin_umul_overflow:
+  case Builtin::BI__builtin_usub_overflow:
+  case Builtin::BI__builtin_uadd_overflow:
+return Ast.UnsignedIntTy;
+  case Builtin::BI__builtin_umull_overflow:
+  case Builtin::BI__builtin_usubl_overflow:
+  case Builtin::BI__builtin_uaddl_overflow:
+return Ast.UnsignedLongTy;
+  case Builtin::BI__builtin_umulll_overflow:
+  case Builtin::BI__builtin_usubll_overflow:
+  case Builtin::BI__builtin_uaddll_overflow:
+return Ast.UnsignedLongLongTy;
+  case Builtin::BI__builtin_mul_overflow:
+  case Builtin::BI__builtin_sub_overflow:
+  case Builtin::BI__builtin_add_overflow:
+return getOverflowBuiltinResultType(Call);
+  default:
+assert(false && "Unknown overflow builtin");
+  }
+}
+
 class BuiltinFunctionChecker : public Checker {
 public:
   bool evalCall(const CallEvent &Call, CheckerContext &C) const;
+  void HandleOverflowBuiltin(const CallEvent &Call, CheckerContext &C,
+ BinaryOperator::Opcode Op,
+ QualType ResultType) const;
 
 private:
   // From: clang/include/clang/Basic/Builtins.def
@@ -50,6 +101,44 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+void BuiltinFunctionChecker::HandleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // All __builtin_*_overflow functions take 3 argumets.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  // TODO: Handle overflows with values that known to overflow. Like INT_MAX + 
1
+  // should not produce state for non-overflow case and threat it as
+  // unreachable.
+
+  // Handle non-overflow case.
+  {
+ProgramStateRef StateSuccess =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs())
+  StateSuccess = StateSuccess->bindLoc(*L, RetVal, C.getLocationContext());
+
+C.addTransition(StateSuccess);
+  }
+
+  // Handle overflow case.
+  {
+C.addTransition(
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(true)));
+  }
+}
+
 bool BuiltinFunctionChecker::isBuiltinLikeFunction(
 const CallEvent &Call) const {
   const auto *FD = llvm::dyn_cast_or_null(Call.getDecl());
@@ -82,10 +171,41 @@ bool BuiltinFunctionChe

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

https://github.com/pskrgag deleted 
https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

@@ -50,6 +101,44 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+void BuiltinFunctionChecker::HandleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // All __builtin_*_overflow functions take 3 argumets.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  // TODO: Handle overflows with values that known to overflow. Like INT_MAX + 
1
+  // should not produce state for non-overflow case and threat it as

pskrgag wrote:

... which turns out to be bad idea, since it depends on `{i,u}128` support.

Will redo with Min/Max

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

https://github.com/pskrgag edited 
https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

https://github.com/pskrgag deleted 
https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

@@ -50,6 +101,44 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+void BuiltinFunctionChecker::HandleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // All __builtin_*_overflow functions take 3 argumets.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  // TODO: Handle overflows with values that known to overflow. Like INT_MAX + 
1
+  // should not produce state for non-overflow case and threat it as

pskrgag wrote:

So I've pushed what I came up with for handling overflow, but during test 
writing I found smth I don't understand. I've decided to push current state, 
since it's easier to show code than describe it =)

My current problem is following code:
```c
   if (a > 10)
 return;
   if (b > 10)
 return;

   // clang_analyzer_eval(a + b < 30); <--- Prints 1 and 0, but why ???

For some reason constraints do not work as expected. And because of that my 
overflow checker splits state where it shouldn't I'd really appreciate tips 

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

@@ -50,6 +101,44 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+void BuiltinFunctionChecker::HandleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // All __builtin_*_overflow functions take 3 argumets.
+  assert(Call.getNumArgs() == 3);

pskrgag wrote:

So I've pushed what I came up with for handling overflow, but during test 
writing I found smth I don't understand. I've decided to push current state, 
since it's easier to show code than describe it =)

My current problem is following code:
```c
   if (a > 10)
 return;
   if (b > 10)
 return;

   // clang_analyzer_eval(a + b < 30); <--- Prints 1 and 0, but why ???

For some reason constraints do not work as expected. And because of that my 
overflow checker splits state where it shouldn't I'd really appreciate tips 

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

https://github.com/pskrgag updated 
https://github.com/llvm/llvm-project/pull/102602

>From 3e0fcffa8fbea5f89ab927fd897c451bcafd8e5e Mon Sep 17 00:00:00 2001
From: Pavel Skripkin 
Date: Fri, 9 Aug 2024 14:37:47 +0300
Subject: [PATCH 1/2] clang/csa: add initial support for builtin overflow

---
 .../Checkers/BuiltinFunctionChecker.cpp   | 124 +-
 clang/test/Analysis/builtin_overflow.c|  65 +
 .../test/Analysis/out-of-bounds-diagnostics.c |  17 +++
 3 files changed, 204 insertions(+), 2 deletions(-)
 create mode 100644 clang/test/Analysis/builtin_overflow.c

diff --git a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp 
b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
index b198b1c2ff4d11..0c8b9fa3d947b0 100644
--- a/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
+++ b/clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp
@@ -21,16 +21,67 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 
+QualType getOverflowBuiltinResultType(const CallEvent &Call) {
+  assert(Call.getNumArgs() == 3);
+
+  return Call.getArgExpr(2)->getType()->getPointeeType();
+}
+
+QualType getOverflowBuiltinResultType(const CallEvent &Call, CheckerContext &C,
+  unsigned BI) {
+  assert(Call.getNumArgs() == 3);
+
+  ASTContext &Ast = C.getASTContext();
+
+  switch (BI) {
+  case Builtin::BI__builtin_smul_overflow:
+  case Builtin::BI__builtin_ssub_overflow:
+  case Builtin::BI__builtin_sadd_overflow:
+return Ast.IntTy;
+  case Builtin::BI__builtin_smull_overflow:
+  case Builtin::BI__builtin_ssubl_overflow:
+  case Builtin::BI__builtin_saddl_overflow:
+return Ast.LongTy;
+  case Builtin::BI__builtin_smulll_overflow:
+  case Builtin::BI__builtin_ssubll_overflow:
+  case Builtin::BI__builtin_saddll_overflow:
+return Ast.LongLongTy;
+  case Builtin::BI__builtin_umul_overflow:
+  case Builtin::BI__builtin_usub_overflow:
+  case Builtin::BI__builtin_uadd_overflow:
+return Ast.UnsignedIntTy;
+  case Builtin::BI__builtin_umull_overflow:
+  case Builtin::BI__builtin_usubl_overflow:
+  case Builtin::BI__builtin_uaddl_overflow:
+return Ast.UnsignedLongTy;
+  case Builtin::BI__builtin_umulll_overflow:
+  case Builtin::BI__builtin_usubll_overflow:
+  case Builtin::BI__builtin_uaddll_overflow:
+return Ast.UnsignedLongLongTy;
+  case Builtin::BI__builtin_mul_overflow:
+  case Builtin::BI__builtin_sub_overflow:
+  case Builtin::BI__builtin_add_overflow:
+return getOverflowBuiltinResultType(Call);
+  default:
+assert(false && "Unknown overflow builtin");
+  }
+}
+
 class BuiltinFunctionChecker : public Checker {
 public:
   bool evalCall(const CallEvent &Call, CheckerContext &C) const;
+  void HandleOverflowBuiltin(const CallEvent &Call, CheckerContext &C,
+ BinaryOperator::Opcode Op,
+ QualType ResultType) const;
 
 private:
   // From: clang/include/clang/Basic/Builtins.def
@@ -50,6 +101,44 @@ class BuiltinFunctionChecker : public Checker {
 
 } // namespace
 
+void BuiltinFunctionChecker::HandleOverflowBuiltin(const CallEvent &Call,
+   CheckerContext &C,
+   BinaryOperator::Opcode Op,
+   QualType ResultType) const {
+  // All __builtin_*_overflow functions take 3 argumets.
+  assert(Call.getNumArgs() == 3);
+
+  ProgramStateRef State = C.getState();
+  SValBuilder &SVB = C.getSValBuilder();
+  const Expr *CE = Call.getOriginExpr();
+
+  SVal Arg1 = Call.getArgSVal(0);
+  SVal Arg2 = Call.getArgSVal(1);
+
+  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
+
+  // TODO: Handle overflows with values that known to overflow. Like INT_MAX + 
1
+  // should not produce state for non-overflow case and threat it as
+  // unreachable.
+
+  // Handle non-overflow case.
+  {
+ProgramStateRef StateSuccess =
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false));
+
+if (auto L = Call.getArgSVal(2).getAs())
+  StateSuccess = StateSuccess->bindLoc(*L, RetVal, C.getLocationContext());
+
+C.addTransition(StateSuccess);
+  }
+
+  // Handle overflow case.
+  {
+C.addTransition(
+State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(true)));
+  }
+}
+
 bool BuiltinFunctionChecker::isBuiltinLikeFunction(
 const CallEvent &Call) const {
   const auto *FD = llvm::dyn_cast_or_null(Call.getDecl());
@@ -82,10 +171,41 @@ bool BuiltinFunctionChe

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

@@ -278,6 +278,23 @@ int *mallocRegion(void) {
   return mem;
 }
 
+int *custom_calloc(size_t a, size_t b) {
+  size_t res;
+  if (__builtin_mul_overflow(a, b, &res))
+return 0;
+
+  return malloc(res);
+}
+
+int *mallocRegionOverflow(void) {
+  int *mem = (int*)custom_calloc(4, 10);
+
+  mem[20] = 10;

pskrgag wrote:

Thanks for note! I've just copy-pasted logic from tests above =)

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Pavel Skripkin via cfe-commits]

@@ -21,16 +21,67 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 
+QualType getOverflowBuiltinResultType(const CallEvent &Call) {
+  assert(Call.getNumArgs() == 3);
+
+  return Call.getArgExpr(2)->getType()->getPointeeType();
+}
+
+QualType getOverflowBuiltinResultType(const CallEvent &Call, CheckerContext &C,
+  unsigned BI) {

pskrgag wrote:

> Is it because its not always present in the declaration of the builting? 

Yeah. If I try `cast(Call.getDecl())->getParamDecl(2)`, then CSA 
crashes, since `Decl` for `builtin`  has 0 params. 

https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[clang] [analyzer] Model overflow builtins (PR #102602)

[Balazs Benics via cfe-commits]

https://github.com/steakhal edited 
https://github.com/llvm/llvm-project/pull/102602
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits