1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
/********************* */
/*! \file query_generator.h
** \verbatim
** Top contributors (to current version):
** Andrew Reynolds
** This file is part of the CVC4 project.
** Copyright (c) 2009-2018 by the authors listed in the file AUTHORS
** in the top-level source directory) and their institutional affiliations.
** All rights reserved. See the file COPYING in the top-level source
** directory for licensing information.\endverbatim
**
** \brief A class for mining interesting satisfiability queries from a stream
** of generated expressions.
**/
#include "cvc4_private.h"
#ifndef __CVC4__THEORY__QUANTIFIERS__QUERY_GENERATOR_H
#define __CVC4__THEORY__QUANTIFIERS__QUERY_GENERATOR_H
#include <map>
#include <unordered_set>
#include "expr/node.h"
#include "theory/quantifiers/expr_miner.h"
#include "theory/quantifiers/lazy_trie.h"
#include "theory/quantifiers/sygus_sampler.h"
namespace CVC4 {
namespace theory {
namespace quantifiers {
/** QueryGenerator
*
* This module is used for finding satisfiable queries that are maximally
* likely to trigger an unsound response in an SMT solver. These queries are
* mined from a stream of enumerated expressions. We judge likelihood of
* triggering unsoundness by the frequency at which the query is satisfied.
*
* In detail, given a stream of expressions t_1, ..., t_{n-1}, upon generating
* term t_n, we consider a query (not) t_n = t_i to be an interesting query
* if it is satisfied by at most D points, where D is a predefined threshold
* given by options::sygusQueryGenThresh(). If t_n has type Bool, we
* additionally consider the case where t_n is satisfied (or not satisfied) by
* fewer than D points.
*
* In addition to generating single literal queries, this module also generates
* conjunctive queries, for instance, by remembering that literals L1 and L2
* were both satisfied by the same point, and thus L1 ^ L2 is an interesting
* query as well.
*/
class QueryGenerator : public ExprMiner
{
public:
QueryGenerator();
~QueryGenerator() {}
/** initialize */
void initialize(const std::vector<Node>& vars,
SygusSampler* ss = nullptr) override;
/**
* Add term to this module. This may trigger the printing and/or checking of
* new queries.
*/
bool addTerm(Node n, std::ostream& out) override;
/**
* Set the threshold value. This is the maximal number of sample points that
* each query we generate is allowed to be satisfied by.
*/
void setThreshold(unsigned deqThresh);
private:
/** cache of all terms registered to this generator */
std::unordered_set<Node, NodeHashFunction> d_terms;
/** the threshold used by this module for maximum number of sat points */
unsigned d_deqThresh;
/**
* For each type, a lazy trie storing the evaluation of all added terms on
* sample points.
*/
std::map<TypeNode, LazyTrie> d_qgtTrie;
/** total number of queries generated by this class */
unsigned d_queryCount;
/** find queries
*
* This function traverses the lazy trie for the type of n, finding equality
* and disequality queries between n and other terms in the trie. The argument
* queries collects the newly generated queries, and the argument
* queriesPtTrue collects the indices of points that each query was satisfied
* by (these indices are the indices of the points in the sampler used by this
* class).
*/
void findQueries(Node n,
std::vector<Node>& queries,
std::vector<std::vector<unsigned>>& queriesPtTrue);
/**
* Maps the index of each sample point to the list of queries that it
* satisfies, and that were generated by the above function. This map is used
* for generating conjunctive queries.
*/
std::map<unsigned, std::vector<Node>> d_ptToQueries;
/**
* Map from queries to the indices of the points that satisfy them.
*/
std::map<Node, std::vector<unsigned>> d_qysToPoints;
/**
* Check query qy, which is satisfied by (at least) sample point spIndex,
* using a separate copy of the SMT engine. Throws an exception if qy is
* reported to be unsatisfiable.
*/
void checkQuery(Node qy, unsigned spIndex);
};
} // namespace quantifiers
} // namespace theory
} // namespace CVC4
#endif /* __CVC4__THEORY__QUANTIFIERS___H */
|
