• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

Alan-Jowett / ebpf-verifier / 18949625295

28 Oct 2025 10:33AM UTC coverage: 87.448% (-1.0%) from 88.47%
18949625295

push

github

elazarg
Bump CLI11 to v2.6.1

Signed-off-by: Elazar Gershuni <elazarg@gmail.com>

9022 of 10317 relevant lines covered (87.45%)

10783407.68 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

86.19
/src/crab/type_domain.cpp
1
// Copyright (c) Prevail Verifier contributors.
2
// SPDX-License-Identifier: MIT
3
// ReSharper disable CppMemberFunctionMayBeStatic
4

5
// This file is eBPF-specific, not derived from CRAB.
6
#include <functional>
7
#include <map>
8
#include <optional>
9

10
#include "arith/dsl_syntax.hpp"
11
#include "arith/variable.hpp"
12
#include "crab/array_domain.hpp"
13
#include "crab/interval.hpp"
14
#include "crab/split_dbm.hpp"
15
#include "crab/type_domain.hpp"
16
#include "crab/type_encoding.hpp"
17
#include "crab/var_registry.hpp"
18
#include "crab_utils/debug.hpp"
19

20
namespace prevail {
21

22
template <is_enum T>
23
static void operator++(T& t) {
408,078✔
24
    t = static_cast<T>(1 + static_cast<std::underlying_type_t<T>>(t));
408,078✔
25
}
408,078✔
26

27
std::vector<DataKind> iterate_kinds(const DataKind lb, const DataKind ub) {
25,294✔
28
    if (lb > ub) {
25,294✔
29
        CRAB_ERROR("lower bound ", lb, " is greater than upper bound ", ub);
×
30
    }
31
    if (lb < KIND_MIN || ub > KIND_MAX) {
25,294✔
32
        CRAB_ERROR("bounds ", lb, " and ", ub, " are out of range");
×
33
    }
34
    std::vector<DataKind> res;
25,294✔
35
    for (DataKind i = lb; i <= ub; ++i) {
278,234✔
36
        res.push_back(i);
252,940✔
37
    }
38
    return res;
25,294✔
39
}
×
40

41
std::vector<TypeEncoding> iterate_types(const TypeEncoding lb, const TypeEncoding ub) {
154,678✔
42
    if (lb > ub) {
154,678✔
43
        CRAB_ERROR("lower bound ", lb, " is greater than upper bound ", ub);
×
44
    }
45
    if (lb < T_MIN || ub > T_MAX) {
154,678✔
46
        CRAB_ERROR("bounds ", lb, " and ", ub, " are out of range");
×
47
    }
48
    std::vector<TypeEncoding> res;
154,678✔
49
    for (TypeEncoding i = lb; i <= ub; ++i) {
309,816✔
50
        res.push_back(i);
155,138✔
51
    }
52
    return res;
154,678✔
53
}
×
54

55
std::vector<TypeEncoding> TypeDomain::iterate_types(const Reg& reg) const {
154,658✔
56
    const Interval allowed_types = inv.eval_interval(reg_type(reg));
154,658✔
57
    if (!allowed_types) {
154,658✔
58
        return {};
×
59
    }
60
    if (allowed_types.contains(T_UNINIT)) {
154,658✔
61
        return {T_UNINIT};
×
62
    }
63
    auto [lb, ub] = allowed_types.bound(T_MIN_VALID, T_MAX);
154,658✔
64
    return prevail::iterate_types(lb, ub);
154,658✔
65
}
154,658✔
66

67
static constexpr auto S_UNINIT = "uninit";
68
static constexpr auto S_STACK = "stack";
69
static constexpr auto S_PACKET = "packet";
70
static constexpr auto S_CTX = "ctx";
71
static constexpr auto S_MAP_PROGRAMS = "map_fd_programs";
72
static constexpr auto S_MAP = "map_fd";
73
static constexpr auto S_NUM = "number";
74
static constexpr auto S_SHARED = "shared";
75

76
std::string name_of(const DataKind kind) {
10,123,038✔
77
    switch (kind) {
10,123,038✔
78
    case DataKind::ctx_offsets: return "ctx_offset";
1,834,736✔
79
    case DataKind::map_fds: return "map_fd";
1,785,644✔
80
    case DataKind::map_fd_programs: return "map_fd_programs";
1,784,184✔
81
    case DataKind::packet_offsets: return "packet_offset";
1,800,276✔
82
    case DataKind::shared_offsets: return "shared_offset";
1,795,832✔
83
    case DataKind::shared_region_sizes: return "shared_region_size";
1,795,832✔
84
    case DataKind::stack_numeric_sizes: return "stack_numeric_size";
1,932,352✔
85
    case DataKind::stack_offsets: return "stack_offset";
1,931,120✔
86
    case DataKind::svalues: return "svalue";
1,796,552✔
87
    case DataKind::types: return "type";
2,052,458✔
88
    case DataKind::uvalues: return "uvalue";
2,182,410✔
89
    }
90
    return {};
×
91
}
92

93
DataKind regkind(const std::string& s) {
4,506✔
94
    static const std::map<std::string, DataKind> string_to_kind{
2,253✔
95
        {"type", DataKind::types},
41✔
96
        {"ctx_offset", DataKind::ctx_offsets},
41✔
97
        {"map_fd", DataKind::map_fds},
41✔
98
        {"map_fd_programs", DataKind::map_fd_programs},
41✔
99
        {"packet_offset", DataKind::packet_offsets},
41✔
100
        {"shared_offset", DataKind::shared_offsets},
41✔
101
        {"stack_offset", DataKind::stack_offsets},
41✔
102
        {"shared_region_size", DataKind::shared_region_sizes},
41✔
103
        {"stack_numeric_size", DataKind::stack_numeric_sizes},
41✔
104
        {"svalue", DataKind::svalues},
41✔
105
        {"uvalue", DataKind::uvalues},
41✔
106
    };
5,531✔
107
    if (string_to_kind.contains(s)) {
4,506✔
108
        return string_to_kind.at(s);
4,506✔
109
    }
110
    throw std::runtime_error(std::string() + "Bad kind: " + s);
×
111
}
82✔
112

113
std::ostream& operator<<(std::ostream& os, const TypeEncoding s) {
1,714✔
114
    switch (s) {
1,714✔
115
    case T_SHARED: return os << S_SHARED;
76✔
116
    case T_STACK: return os << S_STACK;
260✔
117
    case T_PACKET: return os << S_PACKET;
98✔
118
    case T_CTX: return os << S_CTX;
62✔
119
    case T_NUM: return os << S_NUM;
1,202✔
120
    case T_MAP: return os << S_MAP;
12✔
121
    case T_MAP_PROGRAMS: return os << S_MAP_PROGRAMS;
4✔
122
    case T_UNINIT: return os << S_UNINIT;
×
123
    default: CRAB_ERROR("Unsupported type encoding", s);
×
124
    }
125
}
126

127
TypeEncoding string_to_type_encoding(const std::string& s) {
2,572✔
128
    static std::map<std::string, TypeEncoding> string_to_type{
1,286✔
129
        {S_UNINIT, T_UNINIT}, {S_MAP_PROGRAMS, T_MAP_PROGRAMS},
41✔
130
        {S_MAP, T_MAP},       {S_NUM, T_NUM},
82✔
131
        {S_CTX, T_CTX},       {S_STACK, T_STACK},
82✔
132
        {S_PACKET, T_PACKET}, {S_SHARED, T_SHARED},
82✔
133
    };
3,351✔
134
    if (string_to_type.contains(s)) {
2,572✔
135
        return string_to_type[s];
2,572✔
136
    }
137
    throw std::runtime_error(std::string("Unsupported type name: ") + s);
×
138
}
82✔
139

140
Variable reg_type(const Reg& lhs) { return variable_registry->type_reg(lhs.v); }
986,358✔
141

142
void TypeDomain::assign_type(const Reg& lhs, const Reg& rhs) { inv.assign(reg_type(lhs), reg_type(rhs)); }
26,004✔
143

144
void TypeDomain::assign_type(const std::optional<Variable> lhs, const LinearExpression& t) { inv.assign(lhs, t); }
24,210✔
145

146
void TypeDomain::assign_type(const Reg& lhs, const std::optional<LinearExpression>& rhs) {
85,364✔
147
    inv.assign(reg_type(lhs), rhs);
85,364✔
148
}
85,364✔
149

150
void TypeDomain::havoc_type(const Reg& r) { inv.havoc(reg_type(r)); }
70,906✔
151
void TypeDomain::havoc_type(const Variable& v) { inv.havoc(v); }
1,090✔
152

153
TypeEncoding TypeDomain::get_type(const LinearExpression& v) const {
×
154
    const auto res = inv.eval_interval(v).singleton();
×
155
    if (!res) {
×
156
        return T_UNINIT;
157
    }
158
    return res->narrow<TypeEncoding>();
×
159
}
×
160

161
TypeEncoding TypeDomain::get_type(const Reg& r) const {
12,840✔
162
    const auto res = inv.eval_interval(reg_type(r)).singleton();
19,260✔
163
    if (!res) {
12,840✔
164
        return T_UNINIT;
33✔
165
    }
166
    return res->narrow<TypeEncoding>();
12,774✔
167
}
12,840✔
168

169
[[nodiscard]]
170
bool TypeDomain::is_initialized(const Reg& r) const {
265,894✔
171
    using namespace dsl_syntax;
132,947✔
172
    return inv.entail(reg_type(r) != T_UNINIT);
398,841✔
173
}
174

175
[[nodiscard]]
176
bool TypeDomain::is_initialized(const LinearExpression& v) const {
1,258,252✔
177
    using namespace dsl_syntax;
629,126✔
178
    return inv.entail(v != T_UNINIT);
1,887,378✔
179
}
180

181
// Check whether a given type value is within the range of a given type variable's value.
182
bool TypeDomain::may_have_type(const Reg& r, const TypeEncoding type) const {
4✔
183
    const Interval interval = inv.eval_interval(reg_type(r));
4✔
184
    return interval.contains(type);
6✔
185
}
4✔
186

187
bool TypeDomain::may_have_type(const LinearExpression& v, const TypeEncoding type) const {
161,277,391✔
188
    const Interval interval = inv.eval_interval(v);
161,277,391✔
189
    return interval.contains(type);
241,916,730✔
190
}
161,277,391✔
191

192
static LinearConstraint eq_types(const Reg& a, const Reg& b) {
12,409✔
193
    using namespace dsl_syntax;
3,995✔
194
    return eq(reg_type(a), reg_type(b));
12,409✔
195
}
196

197
bool TypeDomain::same_type(const Reg& a, const Reg& b) const { return inv.entail(eq_types(a, b)); }
16,404✔
198

199
bool TypeDomain::is_in_group(const Reg& r, const TypeGroup group) const {
131,624✔
200
    using namespace dsl_syntax;
65,812✔
201
    const Variable t = reg_type(r);
131,624✔
202
    switch (group) {
131,624✔
203
    case TypeGroup::number: return inv.entail(t == T_NUM);
98,685✔
204
    case TypeGroup::map_fd: return inv.entail(t == T_MAP);
6,771✔
205
    case TypeGroup::map_fd_programs: return inv.entail(t == T_MAP_PROGRAMS);
711✔
206
    case TypeGroup::ctx: return inv.entail(t == T_CTX);
8,706✔
207
    case TypeGroup::ctx_or_num: return inv.entail(t == T_CTX) || inv.entail(t == T_NUM);
84✔
208
    case TypeGroup::packet: return inv.entail(t == T_PACKET);
×
209
    case TypeGroup::stack: return inv.entail(t == T_STACK);
×
210
    case TypeGroup::stack_or_num: return inv.entail(t == T_STACK) || inv.entail(t == T_NUM);
×
211
    case TypeGroup::shared: return inv.entail(t == T_SHARED);
×
212
    case TypeGroup::mem: return inv.entail(t >= T_PACKET);
15,512✔
213
    case TypeGroup::mem_or_num: return inv.entail(t >= T_NUM) && inv.entail(t != T_CTX);
2,430✔
214
    case TypeGroup::pointer: return inv.entail(t >= T_CTX);
42,804✔
215
    case TypeGroup::ptr_or_num: return inv.entail(t >= T_NUM);
39,324✔
216
    case TypeGroup::stack_or_packet: return inv.entail(t >= T_PACKET) && inv.entail(t <= T_STACK);
×
217
    case TypeGroup::singleton_ptr: return inv.entail(t >= T_CTX) && inv.entail(t <= T_STACK);
8,932✔
218
    default: CRAB_ERROR("Unsupported type group", group);
×
219
    }
220
}
221

222
std::string typeset_to_string(const std::vector<TypeEncoding>& items) {
52✔
223
    std::stringstream ss;
52✔
224
    ss << "{";
52✔
225
    for (auto it = items.begin(); it != items.end(); ++it) {
192✔
226
        ss << *it;
140✔
227
        if (std::next(it) != items.end()) {
210✔
228
            ss << ", ";
88✔
229
        }
230
    }
231
    ss << "}";
52✔
232
    return ss.str();
104✔
233
}
52✔
234

235
bool is_singleton_type(const TypeGroup t) {
210✔
236
    switch (t) {
210✔
237
    case TypeGroup::number:
91✔
238
    case TypeGroup::map_fd:
239
    case TypeGroup::map_fd_programs:
240
    case TypeGroup::ctx:
241
    case TypeGroup::packet:
242
    case TypeGroup::stack:
243
    case TypeGroup::shared: return true;
91✔
244
    default: return false;
28✔
245
    }
246
}
247

248
std::ostream& operator<<(std::ostream& os, const TypeGroup ts) {
220✔
249
    using namespace prevail;
110✔
250
    static const std::map<TypeGroup, std::string> string_to_type{
110✔
251
        {TypeGroup::number, S_NUM},
2✔
252
        {TypeGroup::map_fd, S_MAP},
2✔
253
        {TypeGroup::map_fd_programs, S_MAP_PROGRAMS},
2✔
254
        {TypeGroup::ctx, S_CTX},
2✔
255
        {TypeGroup::ctx_or_num, typeset_to_string({T_NUM, T_CTX})},
8✔
256
        {TypeGroup::packet, S_PACKET},
4✔
257
        {TypeGroup::stack, S_STACK},
2✔
258
        {TypeGroup::stack_or_num, typeset_to_string({T_NUM, T_STACK})},
8✔
259
        {TypeGroup::shared, S_SHARED},
4✔
260
        {TypeGroup::mem, typeset_to_string({T_STACK, T_PACKET, T_SHARED})},
8✔
261
        {TypeGroup::pointer, typeset_to_string({T_CTX, T_STACK, T_PACKET, T_SHARED})},
8✔
262
        {TypeGroup::ptr_or_num, typeset_to_string({T_NUM, T_CTX, T_STACK, T_PACKET, T_SHARED})},
8✔
263
        {TypeGroup::stack_or_packet, typeset_to_string({T_STACK, T_PACKET})},
8✔
264
        {TypeGroup::singleton_ptr, typeset_to_string({T_CTX, T_STACK, T_PACKET})},
8✔
265
        {TypeGroup::mem_or_num, typeset_to_string({T_NUM, T_STACK, T_PACKET, T_SHARED})},
8✔
266
    };
290✔
267
    if (string_to_type.contains(ts)) {
220✔
268
        return os << string_to_type.at(ts);
220✔
269
    }
270
    CRAB_ERROR("Unsupported type group", ts);
×
271
}
36✔
272

273
} // namespace prevail
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc