pith. sign in

arxiv: 1907.04241 · v1 · pith:3Q4BLHTEnew · submitted 2019-07-08 · 💻 cs.PL · cs.PF

CHOP: Bypassing Runtime Bounds Checking Through Convex Hull OPtimization

Yurong Chen , Hongfa Xue , Tian Lan , Guru Venkataramani This is my paper

Pith reviewed 2026-05-25 00:35 UTC · model grok-4.3

classification 💻 cs.PL cs.PF
keywords bounds checkingconvex hull optimizationmemory safetyprofile-guided optimizationredundant check eliminationSoftBoundC/C++ programsruntime overhead reduction
0
0 comments X

The pith

CHOP derives convex hull models from execution profiles to identify and skip redundant array bounds checks at runtime.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proposes a profile-guided method that builds a knowledge base of sufficient conditions for safe array accesses by treating observed index ranges as points in a convex hull. This lets the system decide at compile time or load time which checks can be omitted without risking memory violations. The approach targets the overhead in tools like SoftBound that insert checks for every access in C and C++ programs. If the models hold, most dynamic checks become unnecessary while preserving safety for the profiled behaviors.

Core claim

For each function, CHOP rapidly derives and updates a knowledge base containing sufficient conditions for identifying redundant array bounds checking by modeling feasible access regions via convex hull optimization on runtime data from past executions, allowing bypass of checks that static analysis cannot eliminate.

What carries the argument

Convex hull optimization applied to runtime index and bound data to compute sufficient conditions for redundant bounds checks.

If this is right

  • An average of 80.12 percent of dynamic bounds check instructions can be avoided across evaluated programs.
  • Performance improves by up to 95.80 percent compared with SoftBound on the same benchmarks.
  • The method applies to real-world applications and standard benchmark suites such as SPEC.
  • A per-function knowledge base can be derived and updated rapidly from profile data.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The technique could reduce the practicality barrier for deploying memory safety instrumentation in performance-sensitive codebases.
  • If profiles are refreshed periodically the same hull construction could adapt to evolving program behavior without full re-analysis.
  • The convex-hull representation might generalize to other runtime invariants such as null-pointer or integer-overflow checks.

Load-bearing premise

Runtime data collected from past program executions is representative of future executions and the convex hull model will correctly identify only truly redundant checks without introducing safety violations.

What would settle it

Running the instrumented program on inputs whose access patterns lie outside the convex hulls derived from the training profiles and observing either a memory safety violation or an incorrect omission of a necessary check.

Figures

Figures reproduced from arXiv: 1907.04241 by Guru Venkataramani, Hongfa Xue, Tian Lan, Yurong Chen.

Figure 1
Figure 1. Figure 1: Runtime overhead for SoftBound compared to original [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 5
Figure 5. Figure 5: System Diagram Future executions that satisfy the conditions of such safe region will be deemed as bound-safe. Note that it is possible that for some functions, we cannot infer the linear relationships among trip counts and function arguments. Hence we cannot perform function-level bounds check decision based on the function arguments, but have to get the values of pointer￾affecting variables inside the fu… view at source ↗
Figure 6
Figure 6. Figure 6: Convex Hull vs Union in a two-dimensional example [PITH_FULL_IMAGE:figures/full_fig_p005_6.png] view at source ↗
Figure 3
Figure 3. Figure 3: We add trip counts tc1, tc2 and tc3 for the three cases in lines 17, 24 and 31, respectively. According to CHOP’s dependency graph construction, there are edges from node tc1, tc2 and tc3 to pointer node cp2. Further, the values of 1We use 5% as threshold to identify Check-HotSpots, while this number can be varied depending on users’ preference. Time spent in Function Non-instrumented version (s) SoftBound… view at source ↗
Figure 7
Figure 7. Figure 7: System framework and Implementation in Pre-Runtime [PITH_FULL_IMAGE:figures/full_fig_p008_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Comparison of normalized execution time overhead [PITH_FULL_IMAGE:figures/full_fig_p009_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Comparison of bounds check removal ratio between [PITH_FULL_IMAGE:figures/full_fig_p009_9.png] view at source ↗
read the original abstract

Unsafe memory accesses in programs written using popular programming languages like C/C++ have been among the leading causes for software vulnerability. Prior memory safety checkers such as SoftBound enforce memory spatial safety by checking if every access to array elements are within the corresponding array bounds. However, it often results in high execution time overhead due to the cost of executing the instructions associated with bounds checking. To mitigate this problem, redundant bounds check elimination techniques are needed. In this paper, we propose CHOP, a Convex Hull OPtimization based framework, for bypassing redundant memory bounds checking via profile-guided inferences. In contrast to existing check elimination techniques that are limited by static code analysis, our solution leverages a model-based inference to identify redundant bounds checking based on runtime data from past program executions. For a given function, it rapidly derives and updates a knowledge base containing sufficient conditions for identifying redundant array bounds checking. We evaluate CHOP on real-world applications and benchmark (such as SPEC) and the experimental results show that on average 80.12% of dynamic bounds check instructions can be avoided, resulting in improved performance up to 95.80% over SoftBound.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper proposes CHOP, a profile-guided framework that uses convex hull optimization on runtime execution data to derive sufficient conditions for eliminating redundant array bounds checks in C/C++ programs. It claims that this approach avoids an average of 80.12% of dynamic bounds check instructions, yielding performance improvements of up to 95.80% relative to SoftBound on SPEC benchmarks and real-world applications.

Significance. If the central soundness claim holds, the work would offer a practical method for lowering the overhead of spatial memory safety enforcement without requiring changes to static analysis. The profile-driven convex hull model could complement existing tools, but the absence of a soundness argument or coverage guarantees for the derived conditions limits the result's immediate impact.

major comments (3)
  1. [Abstract] Abstract: the claim that runtime-derived convex hulls yield 'sufficient conditions' for safely bypassing checks is not accompanied by any argument that the hull is a sound over-approximation of all possible index expressions; finite profile runs can miss inputs that would produce out-of-bounds accesses once the static check is removed.
  2. The experimental claims (80.12% check elimination, 95.80% speedup) rest on the assumption that profile data is representative, yet the manuscript supplies no validation of the convex hull model, no false-negative rates for eliminated checks, and no discussion of runtime guards that would restore safety when an execution falls outside the observed hull.
  3. The method description does not specify how the convex hull is updated across multiple profile runs or whether the 'knowledge base' of sufficient conditions is ever re-checked against new executions, leaving open the possibility that later inputs invalidate earlier eliminations.
minor comments (2)
  1. The abstract and evaluation sections should clarify the exact definition of 'dynamic bounds check instructions' and how they are counted relative to the SoftBound baseline.
  2. Notation for the convex hull construction (e.g., how points are extracted from index expressions) is introduced without an accompanying formal definition or small illustrative example.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive comments. The feedback correctly notes that CHOP is a profile-guided optimization rather than a fully sound static technique. We address each point below and will revise the manuscript to improve clarity on assumptions and limitations.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the claim that runtime-derived convex hulls yield 'sufficient conditions' for safely bypassing checks is not accompanied by any argument that the hull is a sound over-approximation of all possible index expressions; finite profile runs can miss inputs that would produce out-of-bounds accesses once the static check is removed.

    Authors: CHOP derives sufficient conditions from observed runtime profiles via convex hull optimization. These conditions are sufficient for the profiled executions but are not presented as a sound over-approximation of all possible index expressions. The technique is profile-guided by design. We will revise the abstract and add a limitations subsection explicitly stating the reliance on representative profiles and the possibility that unseen inputs may violate the hull. revision: yes

  2. Referee: The experimental claims (80.12% check elimination, 95.80% speedup) rest on the assumption that profile data is representative, yet the manuscript supplies no validation of the convex hull model, no false-negative rates for eliminated checks, and no discussion of runtime guards that would restore safety when an execution falls outside the observed hull.

    Authors: The reported elimination rates and speedups are measured on the profiled executions used to construct the hulls. We do not supply false-negative rates because the method does not claim soundness for unprofiled inputs. We will add discussion of the representative-profile assumption and the deliberate absence of runtime guards (which would eliminate the performance gain). No additional model validation beyond the reported benchmark results will be added. revision: partial

  3. Referee: The method description does not specify how the convex hull is updated across multiple profile runs or whether the 'knowledge base' of sufficient conditions is ever re-checked against new executions, leaving open the possibility that later inputs invalidate earlier eliminations.

    Authors: Section 3 describes incremental construction of the knowledge base from profile data. We will expand this description to clarify how convex hulls from multiple profile runs are merged and to state explicitly that re-checking against new executions is outside the current design, as the derived conditions are applied statically after profiling. revision: yes

Circularity Check

0 steps flagged

No significant circularity; results are empirical from external profile data

full rationale

The paper derives its claims from profile-guided convex hull construction on runtime data collected from past executions, followed by experimental measurement of check elimination rates on SPEC and real-world applications. No step reduces by construction to fitted parameters, self-citations, or definitional renaming; the 80.12% avoidance figure is an observed outcome on benchmark inputs rather than a tautology of the model's equations. The approach is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The approach depends on runtime profile data being representative and on the convex hull model accurately capturing bounds conditions; no explicit free parameters or invented entities are described in the abstract.

free parameters (1)
  • Profile-derived thresholds for redundant checks
    Conditions for skipping checks are inferred from runtime data, which implicitly involves choices about what constitutes sufficient evidence of redundancy.
axioms (1)
  • domain assumption Runtime profiles from past executions are representative of future program behavior
    The profile-guided inference for redundant check elimination depends on this assumption holding for the knowledge base to remain safe.

pith-pipeline@v0.9.0 · 5738 in / 1232 out tokens · 30580 ms · 2026-05-25T00:35:47.313174+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

42 extracted references · 42 canonical work pages · 1 internal anchor

  1. [1]

    Cve-2015-7547: glibc getaddrinfo stack-based buffer overflow,

    Google, “Cve-2015-7547: glibc getaddrinfo stack-based buffer overflow,” https://security.googleblog.com/2016/02/ cve-2015-7547-glibc-getaddrinfo-stack.html

    work page 2015

  2. [2]

    Cve-2016-1287: Cisco asa software ikev1 and ikev2 buffer overflow vulnerability,

    Cisco, “Cve-2016-1287: Cisco asa software ikev1 and ikev2 buffer overflow vulnerability,” https://tools.cisco.com/security/center/content/ CiscoSecurityAdvisory/cisco-sa-20160210-asa-ike

    work page 2016

  3. [3]

    Softbound: Highly compatible and complete spatial memory safety for c,

    S. Nagarakatte, J. Zhao, M. M. Martin, and S. Zdancewic, “Softbound: Highly compatible and complete spatial memory safety for c,” vol. 44, no. 6. ACM, 2009, pp. 245–258

    work page 2009

  4. [4]

    Abcd: eliminating array bounds checking on demand,

    R. Bod ´ık, R. Gupta, and V . Sarkar, “Abcd: eliminating array bounds checking on demand,” in ACM SIGPLAN Notices, vol. 35, no. 5. ACM, 2000, pp. 321–333

    work page 2000

  5. [5]

    Eliminating redundant bounds check- ing in dynamic buffer overflow detection using weakest preconditions,

    Y . Sui, D. Ye, Y . Su, and J. Xue, “Eliminating redundant bounds check- ing in dynamic buffer overflow detection using weakest preconditions,” IEEE Transactions on Reliability , vol. 65, no. 4, 2016

    work page 2016

  6. [6]

    Simber: Eliminating redundant memory bound checks via statistical inference,

    H. Xue, Y . Chen, F. Yao, Y . Li, T. Lan, and G. Venkataramani, “Simber: Eliminating redundant memory bound checks via statistical inference,” in Proceedings of the IFIP International Conference on Computer Security. Springer, 2017

    work page 2017

  7. [7]

    Spec cpu 2006,

    “Spec cpu 2006,” https://www.spec.org/cpu2006/. 14

    work page 2006

  8. [8]

    The quickhull algorithm for convex hulls,

    C. B. Barber, D. P. Dobkin, and H. Huhdanpaa, “The quickhull algorithm for convex hulls,” ACM Trans. Math. Softw. , vol. 22, no. 4, pp. 469–483, Dec. 1996. [Online]. Available: http://doi.acm.org/10. 1145/235815.235821

    work page arXiv 1996

  9. [9]

    The new linuxperftools,

    A. C. de Melo, “The new linuxperftools,” in Slides from Linux Kongress, vol. 18, 2010

    work page 2010

  10. [10]

    Pscan: A limited problem scanner for c source files,

    D. Alan, “Pscan: A limited problem scanner for c source files,” http: //deployingradius.com/pscan/

    work page

  11. [11]

    Improving security using extensible lightweight static analysis,

    D. Evans and D. Larochelle, “Improving security using extensible lightweight static analysis,” IEEE software, vol. 19, no. 1, 2002

    work page 2002

  12. [12]

    Pr-miner: automatically extracting implicit program- ming rules and detecting violations in large software code,

    Z. Li and Y . Zhou, “Pr-miner: automatically extracting implicit program- ming rules and detecting violations in large software code,” in ACM SIGSOFT Software Engineering Notes , vol. 30, no. 5. ACM, 2005

    work page 2005

  13. [13]

    A security policy oracle: Detecting security holes using multiple api implementations,

    V . Srivastava, M. D. Bond, K. S. McKinley, and V . Shmatikov, “A security policy oracle: Detecting security holes using multiple api implementations,” ACM SIGPLAN Notices , vol. 46, no. 6, 2011

    work page 2011

  14. [14]

    Generalized vulnerability extrapolation using abstract syntax trees,

    F. Yamaguchi, M. Lottmann, and K. Rieck, “Generalized vulnerability extrapolation using abstract syntax trees,” in Annual Computer Security Applications Conference, 2012

    work page 2012

  15. [15]

    Joern: A robust code analysis platform for c/c++,

    F. Yamaguchi, “Joern: A robust code analysis platform for c/c++,” http: //www.mlsec.org/joern/

    work page

  16. [16]

    Modeling and discover- ing vulnerabilities with code property graphs,

    F. Yamaguchi, N. Golde, D. Arp, and K. Rieck, “Modeling and discover- ing vulnerabilities with code property graphs,” in 2014 IEEE Symposium on Security and Privacy . IEEE, 2014, pp. 590–604

    work page 2014

  17. [17]

    Automatic infer- ence of search patterns for taint-style vulnerabilities,

    F. Yamaguchi, A. Maier, H. Gascon, and K. Rieck, “Automatic infer- ence of search patterns for taint-style vulnerabilities,” in 2015 IEEE Symposium on Security and Privacy . IEEE, 2015, pp. 797–812

    work page 2015

  18. [18]

    Owens and G

    M. Owens and G. Allen, SQLite. Springer, 2010

    work page 2010

  19. [19]

    Fuzzing: the state of the art,

    R. McNally, K. Yiu, D. Grove, and D. Gerhardy, “Fuzzing: the state of the art,” DTIC Document, Tech. Rep., 2012

    work page 2012

  20. [20]

    Scheduling black- box mutational fuzzing,

    M. Woo, S. K. Cha, S. Gottlieb, and D. Brumley, “Scheduling black- box mutational fuzzing,” in ACM SIGSAC conference on Computer & communications security, 2013

    work page 2013

  21. [21]

    The sphinx-ii speech recognition system: an overview,

    X. Huang, F. Alleva, H.-W. Hon, M.-Y . Hwang, K.-F. Lee, and R. Rosen- feld, “The sphinx-ii speech recognition system: an overview,” Computer Speech & Language , vol. 7, no. 2, pp. 137–148, 1993

    work page 1993

  22. [22]

    Interprocedural analysis with lazy propagation,

    S. H. Jensen, A. Møller, and P. Thiemann, “Interprocedural analysis with lazy propagation,” in International Static Analysis Symposium . Springer, 2010, pp. 320–339

    work page 2010

  23. [23]

    Svf: Interprocedural static value-flow analysis in llvm,

    Y . Sui and J. Xue, “Svf: Interprocedural static value-flow analysis in llvm,” in Proceedings of the 25th International Conference on Compiler Construction, ser. CC 2016. New York, NY , USA: ACM, 2016, pp. 265–

    work page 2016

  24. [24]

    Available: http://doi.acm.org/10.1145/2892208.2892235

    [Online]. Available: http://doi.acm.org/10.1145/2892208.2892235

    work page doi:10.1145/2892208.2892235

  25. [25]

    SoK: Sanitizing for Security

    D. Song, J. Lettner, P. Rajasekaran, Y . Na, S. V olckaert, P. Larsen, and M. Franz, “Sok: sanitizing for security,” arXiv preprint arXiv:1806.04355, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  26. [26]

    Exploring dynamic re- dundancy to resuscitate faulty pcm blocks,

    J. Chen, G. Venkataramani, and H. H. Huang, “Exploring dynamic re- dundancy to resuscitate faulty pcm blocks,” J. Emerg. Technol. Comput. Syst., vol. 10, no. 4, Jun. 2014

    work page 2014

  27. [27]

    Deft: Design space exploration for on-the-fly detection of coherence misses,

    G. Venkataramani, C. J. Hughes, S. Kumar, and M. Prvulovic, “Deft: Design space exploration for on-the-fly detection of coherence misses,” ACM Transactions on Architecture and Code Optimization (TACO) , vol. 8, no. 2, p. 8, 2011

    work page 2011

  28. [28]

    Repram: Re-cycling pram faulty blocks for extended lifetime,

    J. Chen, G. Venkataramani, and H. H. Huang, “Repram: Re-cycling pram faulty blocks for extended lifetime,” in IEEE/IFIP International Conference on Dependable Systems and Networks , 2012

    work page 2012

  29. [29]

    Lime: A framework for debugging load imbalance in multi-threaded execution,

    J. Oh, C. J. Hughes, G. Venkataramani, and M. Prvulovic, “Lime: A framework for debugging load imbalance in multi-threaded execution,” in 33rd International Conference on Software Engineering. ACM, 2011

    work page 2011

  30. [30]

    Buffer overrun detection using linear programming and static analysis,

    V . Ganapathy, S. Jha, D. Chandler, D. Melski, and D. Vitek, “Buffer overrun detection using linear programming and static analysis,” in Pro- ceedings of the 10th ACM conference on Computer and communications security. ACM, 2003, pp. 345–354

    work page 2003

  31. [31]

    Chucky: Exposing missing checks in source code for vulnerability discovery,

    F. Yamaguchi, C. Wressnegger, H. Gascon, and K. Rieck, “Chucky: Exposing missing checks in source code for vulnerability discovery,” in ACM Conference on Computer & Communications security , 2013

    work page 2013

  32. [32]

    Cssv: Towards a realistic tool for statically detecting all buffer overflows in c,

    N. Dor, M. Rodeh, and M. Sagiv, “Cssv: Towards a realistic tool for statically detecting all buffer overflows in c,” in ACM Sigplan Notices , vol. 38, no. 5. ACM, 2003, pp. 155–167

    work page 2003

  33. [33]

    Clone-hunter: accelerated bound checks elimination via binary code clone detection,

    H. Xue, G. Venkataramani, and T. Lan, “Clone-hunter: accelerated bound checks elimination via binary code clone detection,” in Proceed- ings of the 2nd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages . ACM, 2018, pp. 11–19

    work page 2018

  34. [34]

    Ccured: Type-safe retrofitting of legacy code,

    G. C. Necula, S. McPeak, and W. Weimer, “Ccured: Type-safe retrofitting of legacy code,” vol. 37, no. 1, pp. 128–139, 2002

    work page 2002

  35. [35]

    Tradeoffs in fine- grained heap memory protection,

    J. Shen, G. Venkataramani, and M. Prvulovic, “Tradeoffs in fine- grained heap memory protection,” in Proceedings of the 1st workshop on Architectural and system support for improving software dependability . ACM, 2006, pp. 52–57

    work page 2006

  36. [36]

    Preventing memory error exploits with wit,

    P. Akritidis, C. Cadar, C. Raiciu, M. Costa, and M. Castro, “Preventing memory error exploits with wit,” in 2008 IEEE Symposium on Security and Privacy (sp 2008) . IEEE, 2008, pp. 263–277

    work page 2008

  37. [37]

    Sarre: semantics-aware rule recommendation and enforcement for event paths on android,

    Y . Li, F. Yao, T. Lan, and G. Venkataramani, “Sarre: semantics-aware rule recommendation and enforcement for event paths on android,” IEEE Tran. on Information Forensics and Security , vol. 11, no. 12, 2016

    work page 2016

  38. [38]

    Damgate: Dynamic adaptive multi-feature gating in program binaries,

    Y . Chen, T. Lan, and G. Venkataramani, “Damgate: Dynamic adaptive multi-feature gating in program binaries,” in Proceedings of the 2017 Workshop on Forming an Ecosystem Around Software Transformation . ACM, 2017, pp. 23–29

    work page 2017

  39. [39]

    Mem- tracker: An accelerator for memory debugging and monitoring,

    G. Venkataramani, I. Doudalis, Y . Solihin, and M. Prvulovic, “Mem- tracker: An accelerator for memory debugging and monitoring,” ACM Transactions on Architecture and Code Optimization (TACO) , vol. 6, no. 2, p. 5, 2009

    work page 2009

  40. [40]

    Effective and efficient memory protection using dynamic tainting,

    I. Doudalis, J. Clause, G. Venkataramani, M. Prvulovic, and A. Orso, “Effective and efficient memory protection using dynamic tainting,” IEEE Transactions on Computers , vol. 61, no. 1, pp. 87–100, 2012

    work page 2012

  41. [41]

    StatSym: Vulnerable Path Discovery through Statistics-guided Symbolic Execu- tion,

    F. Yao, Y . Li, Y . Chen, H. Xue, G. Venkataramani, and T. Lan, “StatSym: Vulnerable Path Discovery through Statistics-guided Symbolic Execu- tion,” in IEEE/IFIP International Conference on Dependable Systems and Networks, 2017

    work page 2017

  42. [42]

    Array bounds check elimination for the java hotspot client compiler,

    T. W ¨urthinger, C. Wimmer, and H. M ¨ossenb¨ock, “Array bounds check elimination for the java hotspot client compiler,” in Proceedings of the 5th international symposium on Principles and practice of programming in Java. ACM, 2007, pp. 125–133

    work page 2007