检索结果-内蒙古大学图书馆

34th IEEE/ACM International Conference on Automated Software Engineering (ASE)

作者： Eiers, William Saha, Seemanta Brennan, Tegan Bultan, Tevfik UC Santa Barbara Verificat Lab Santa Barbara CA 93106 USA

ISBN: (纸本)9781728125084

quantitative program analysis is an emerging area with applications to software reliability, quantitative information flow, side-channel detection and attack synthesis. Most quantitative program analysis techniques rely on model counting constraint solvers, which are typically the bottleneck for scalability. Although the effectiveness of formula caching in expediting expensive model-counting queries has been demonstrated in prior work, our key insight is that many subformulas are shared across non-identical constraints generated during program analyses. This has not been utilized by prior formula caching approaches. In this paper we present a subformula caching framework and integrate it into a model counting constraint solver. We experimentally evaluate its effectiveness under three quantitative program analysis scenarios: 1) model counting constraints generated by symbolic execution, 2) reliability analysis using probabilistic symbolic execution, 3) adaptive attack synthesis for side-channels. Our experimental results demonstrate that our subformula caching approach significantly improves the performance of quantitative program analysis.

关键词： formula caching model counting quantitative program analysis

来源：评论

学校读者我要写书评

暂无评论

Subformula caching for model counting and quantitative program analysis 19

Subformula caching for model counting and quantitative progr...

引用

Proceedings of the 34th IEEE/ACM International Conference on Automated Software Engineering

作者： William Eiers Seemanta Saha Tegan Brennan Tevfik Bultan UC Santa Barbara

ISBN: (纸本)9781728125084

关键词： formula caching model counting quantitative program analysis

来源：评论

学校读者我要写书评

暂无评论

Constraint Normalization and Parameterized Caching for quantitative program analysis 2017

Constraint Normalization and Parameterized Caching for Quant...

引用

11th Joint Meeting of European Software Engineering Conference (ESEC) / ACM SIGSOFT Symposium on the Foundations of Software Engineering (FSE)

作者： Brennan, Tegan Tsiskaridze, Nestan Rosner, Nicolas Aydin, Abdulbaki Bultan, Tevfik Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA

ISBN: (纸本)9781450351058

We present a constraint caching framework to expedite potentially expensive satisfiability and model-counting queries. Integral to this framework is our new constraint normalization procedure under which the cardinality of the solution set of a constraint, but not necessarily the solution set itself, is preserved. We extend these constraint normalization techniques to string constraints in order to support analysis of string-manipulating code. We use a group-theoretic framework, which generalizes earlier results, to express our normalization techniques. We also present a parameterized caching approach where, in addition to storing the result of a model-counting query, we store a model-counter object that allows us to efficiently recount the number of satisfying models for different bounds. We implement these techniques in our tool Cashew, which is built as an extension of the Green caching framework [55], and integrate it with the symbolic execution tool Symbolic PathFinder (SPF) and the model-counting constraint solver ABC. Our experiments show that constraint caching can significantly improve the performance of symbolic and quantitative program analyses. For instance, Cashew can normalize the 10,104 unique constraints in the SMC/Kaluza benchmark down to 394 normal forms, achieve a 10x speedup on the SMC/Kaluza-Big dataset, and an average 3x speedup in our SPF-based side-channel analysis experiments.

关键词： Constraint caching quantitative program analysis model counting string constraints

来源：评论

学校读者我要写书评

暂无评论

Obtaining Information Leakage Bounds via Approximate Model Counting

引用

PROCEEDINGS OF THE ACM ON programMING LANGUAGES-PACMPL 2023年第PLDI期7卷 1488-1509页

作者： Saha, Seemanta Ghentiyala, Surendra Lu, Shihua Bang, Lucas Bultan, Tevfik Univ Calif Santa Barbara Santa Barbara CA 93106 USA Harvey Mudd Coll Claremont CA USA

Information leaks are a significant problem in modern software systems. In recent years, information theoretic concepts, such as Shannon entropy, have been applied to quantifying information leaks in programs. One recent approach is to use symbolic execution together with model counting constraints solvers in order to quantify information leakage. There are at least two reasons for unsoundness in quantifying information leakage using this approach: 1) Symbolic execution may not be able to explore all execution paths, 2) Model counting constraints solvers may not be able to provide an exact count. We present a sound symbolic quantitative information flow analysis that bounds the information leakage both for the cases where the program behavior is not fully explored and the model counting constraint solver is unable to provide a precise model count but provides an upper and a lower bound. We implemented our approach as an extension to KLEE for computing sound bounds for information leakage in C programs.

关键词： quantitative program analysis Symbolic quantitative Information Flow analysis Model Counting Information Leakage Optimization

来源：评论

学校读者我要写书评

暂无评论

Quantifying Information Leakage Using Model Counting Constraint Solvers 1

引用

11th International Working Conference on Verified Software - Theories, Tools, and Experiments (VSTTE)

作者： Bultan, Tevfik Univ Calif Santa Barbara Santa Barbara CA 93106 USA

ISBN: (数字)9783030416003

ISBN: (纸本)9783030416003;9783030415990

This paper provides a brief overview of recent results in quantitative information flow analysis, model counting constraints solvers, side-channel analysis and attack synthesis. By combining model counting constraints solvers with symbolic execution it is possible to quantify the amount of information that a program leaks about a secret input. As discussed below, this type of analysis is crucial for detection and analysis of side channel vulnerabilities.

关键词： quantitative program analysis Model counting quantitative information flow Side channels

来源：评论

学校读者我要写书评

暂无评论

Accurate String Constraints Solution Counting with Weighted Automata 34

Accurate String Constraints Solution Counting with Weighted ...

引用

34th IEEE/ACM International Conference on Automated Software Engineering (ASE)

作者： Sherman, Elena Harris, Andrew Boise State Univ Comp Sci Dept Boise ID 83725 USA

ISBN: (纸本)9781728125084

As an important extension of symbolic execution (SE), probabilistic symbolic execution (PSE) computes execution probabilities of program paths. Using this information, PSE can prioritize path exploration strategies. To calculate the probability of a path PSE relies on solution counting approaches for the path constraint. The correctness of a solution counting approach depends on the methodology used to count solutions and whether a path constraint maintains a one-to-one relation with program input values. This work focuses on the latter aspect of the solution counting correctness for string constraints. In general, maintaining a one-to-one relation is not always possible, especially in the presence of non-linear constraints. To deal with this issue, researchers that work on PSE for numerical domains either analyze programs with linear constraints, or develop novel techniques to handle solution counting of non-linear constraints. For the string domain, however, previous work on PSE mainly focuses on efficient and accurate solution counting for automata-based string models and has not investigated whether a one-to-one relationship between the strings encoded by automata and input string values is preserved. In this work we demonstrate that traditional automata-based string models fail to maintain one-to-one relations and propose to use the weighted automata model, which preserves the one-to-one relation between the path constraint it encodes and the input string values. We use this model to implement a string constraint solver and show its correctness on a set of non-trivial synthetic benchmarks. We also present an empirical evaluation of traditional and proposed automata solvers on real-world string constraints. The evaluations show that while being less efficient than traditional automata models, the weighted automata model maintains correct solution counts.

关键词： probabilistic symbolic execution string constraints quantitative program analysis

来源：评论

学校读者我要写书评

暂无评论

Accurate string constraints solution counting with weighted automata 19

Accurate string constraints solution counting with weighted ...

引用

Proceedings of the 34th IEEE/ACM International Conference on Automated Software Engineering

作者： Elena Sherman Andrew Harris Boise State University

ISBN: (纸本)9781728125084

As an important extension of symbolic execution (SE), probabilistic symbolic execution (PSE) computes execution probabilities of program paths. Using this information, PSE can prioritize path exploration strategies. To calculate the probability of a path PSE relies on solution counting approaches for the path constraint. The correctness of a solution counting approach depends on the methodology used to count solutions and whether a path constraint maintains a one-to-one relation with program input values. This work focuses on the latter aspect of the solution counting correctness for string *** general, maintaining a one-to-one relation is not always possible, especially in the presence of non-linear constraints. To deal with this issue, researchers that work on PSE for numerical domains either analyze programs with linear constraints, or develop novel techniques to handle solution counting of nonlinear constraints. For the string domain, however, previous work on PSE mainly focuses on efficient and accurate solution counting for automata-based string models and has not investigated whether a one-to-one relationship between the strings encoded by automata and input string values is preserved. In this work we demonstrate that traditional automata-based string models fail to maintain one-to-one relations and propose to use the weighted automata model, which preserves the one-to-one relation between the path constraint it encodes and the input string values. We use this model to implement a string constraint solver and show its correctness on a set of non-trivial synthetic benchmarks. We also present an empirical evaluation of traditional and proposed automata solvers on real-world string constraints. The evaluations show that while being less efficient than traditional automata models, the weighted automata model maintains correct solution counts.

关键词： quantitative program analysis probabilistic symbolic execution string constraints

来源：评论

学校读者我要写书评

暂无评论

Parameterized Model Counting for String and Numeric Constraints 2018

Parameterized Model Counting for String and Numeric Constrai...

引用

26th ACM Joint Meeting on European Software Engineering Conference (ESEC) / Symposium on the Foundations of Software Engineering (FSE)

作者： Aydin, Abdulbaki Eiers, William Bang, Lucas Brennan, Tegan Gavrilov, Miroslav Bultan, Tevfik Yu, Fang Microsoft Redmond WA 98052 USA Univ Calif Santa Barbara Santa Barbara CA 93106 USA Natl Chengchi Univ Taipei Taiwan

ISBN: (纸本)9781450355735

Recently, symbolic program analysis techniques have been extended to quantitative analyses using model counting constraint solvers. Given a constraint and a bound, a model counting constraint solver computes the number of solutions for the constraint within the bound. We present a parameterized model counting constraint solver for string and numeric constraints. We first construct a multi-track deterministic finite state automaton that accepts all solutions to the given constraint. We limit the numeric constraints to linear integer arithmetic, and for non-regular string constraints we over-approximate the solution set. Counting the number of accepting paths in the generated automaton solves the model counting problem. Our approach is parameterized in the sense that, we do not assume a finite domain size during automata construction, resulting in a potentially infinite set of solutions, and our model counting approach works for arbitrarily large bounds. We experimentally demonstrate the effectiveness of our approach on a large set of string and numeric constraints extracted from software applications. We experimentally compare our tool to five existing model counting constraint solvers for string and numeric constraints and demonstrate that our tool is as efficient and as or more precise than other solvers. Moreover, our tool can handle mixed constraints with string and integer variables that no other tool can.

关键词： Model counting constraint solving quantitative program analysis

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：