Skip to content

Commit da77deb

Browse files
author
Juan José López Jaimez
committed
implement the minimizer of PoCs
1 parent 53f72dc commit da77deb

6 files changed

Lines changed: 261 additions & 5 deletions

File tree

‎pkg/ebpf/instruction_generators.go‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -17,6 +17,7 @@ package ebpf
1717
import (
1818
"buzzer/pkg/rand"
1919
pb "buzzer/proto/ebpf_go_proto"
20+
protobuf "github.com/golang/protobuf/proto"
2021
)
2122

2223
// GenerateRandomAluInstruction provides a random ALU operation with either
@@ -234,3 +235,12 @@ func generateRegAluInstruction(op pb.AluOperationCode, insClass pb.InsClass, dst
234235

235236
return newAluInstruction(op, insClass, dstReg, srcReg)
236237
}
238+
239+
func DuplicateProgram(prog []*pb.Instruction) []*pb.Instruction {
240+
ret := []*pb.Instruction{}
241+
for _, ins := range prog {
242+
insCp := protobuf.Clone(ins).(*pb.Instruction)
243+
ret = append(ret, insCp)
244+
}
245+
return ret
246+
}

‎pkg/ebpf/poc_generator.go‎

Lines changed: 156 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -19,12 +19,11 @@ import (
1919
"errors"
2020
"fmt"
2121
jsonpb "github.com/golang/protobuf/jsonpb"
22+
protobuf "github.com/golang/protobuf/proto"
2223
"os"
2324
)
2425

25-
// GeneratePoc generates a c program that can be used to reproduce fuzzer
26-
// test cases.
27-
func GeneratePoc(program *pb.Program) error {
26+
func writeJsonProgram(program *pb.Program) error {
2827
m := &jsonpb.Marshaler{
2928
OrigName: true,
3029
EnumsAsInts: false,
@@ -43,5 +42,159 @@ func GeneratePoc(program *pb.Program) error {
4342
fmt.Printf("Writing eBPF PoC %q.\n", f.Name())
4443
_, err = f.Write([]byte(textpbData))
4544
return errors.Join(err, f.Close())
45+
}
46+
47+
func copyProgram(program *pb.Program) *pb.Program {
48+
return protobuf.Clone(program).(*pb.Program)
49+
}
50+
51+
func Minimizer(program *pb.Program, bugCheckFunction func(*pb.Program) bool, footerSize int) (*pb.Program, error) {
52+
fmt.Println("Running minimizer...")
53+
minimalProgram := copyProgram(program)
54+
minimalProgramInstructions := DuplicateProgram(program.Functions[0].Instructions)
55+
if footerSize > len(minimalProgramInstructions) {
56+
return nil, fmt.Errorf("footerSize > len(program) (%d vs %d)", footerSize, len(minimalProgramInstructions))
57+
}
58+
59+
minimalProgram.Functions[0].Instructions = minimalProgramInstructions
60+
noop := Jmp(0)
61+
62+
phase1 := func() bool {
63+
// First step: change all instructions not contributing to the bug
64+
// to be noops.
65+
changed := true
66+
fmt.Println("Step 1: noop'ing instructions")
67+
roundCount := 1
68+
nooped := 0
69+
for changed {
70+
changed = false
71+
for i := 0; i < len(minimalProgramInstructions)-footerSize; i++ {
72+
fmt.Printf("\tattempting to noop instruction: %d (of %d), nooped: %d \r", i, len(minimalProgramInstructions), nooped)
73+
prev := minimalProgramInstructions[i]
74+
75+
// Don't process any previous noops
76+
if protobuf.Equal(prev, noop) {
77+
continue
78+
}
79+
80+
// Replace instruction with a noop
81+
minimalProgramInstructions[i] = noop
82+
if bugCheckFunction(minimalProgram) {
83+
changed = true
84+
nooped += 1
85+
} else {
86+
minimalProgramInstructions[i] = prev
87+
}
88+
}
89+
fmt.Printf("\n\tround %d finished\n", roundCount)
90+
roundCount += 1
91+
}
92+
return nooped != 0
93+
}
94+
95+
phase2 := func() bool {
96+
changesDone := false
97+
// Second step: reduce the jumps to a minimum offset.
98+
fmt.Println("--------------------------------------")
99+
fmt.Println("Step 2: minimizing jumps")
100+
for i := 0; i < len(minimalProgramInstructions); i++ {
101+
insn := minimalProgramInstructions[i]
102+
switch insn.Opcode.(type) {
103+
case *pb.Instruction_JmpOpcode:
104+
if insn.Offset == 0 {
105+
continue
106+
}
107+
previousOffset := insn.Offset
108+
insn.Offset -= 1
109+
fmt.Printf("\tminimizing offset of instruction %d (initial: %d)\n", i, previousOffset)
110+
for bugCheckFunction(minimalProgram) && insn.Offset != 0 {
111+
changesDone = true
112+
previousOffset = insn.Offset
113+
insn.Offset -= 1
114+
fmt.Printf("\t\treducing offset to: %d \r", insn.Offset)
115+
}
116+
fmt.Printf("\t\tfound minimal offset: %d \n", previousOffset)
117+
insn.Offset = previousOffset
118+
default:
119+
continue
120+
}
121+
}
122+
return changesDone
123+
}
124+
phase3 := func() (bool, []*pb.Instruction) {
125+
fmt.Println("--------------------------------------")
126+
fmt.Println("Step 3: removing noop instructions")
127+
removed := 0
128+
minimalModified := []*pb.Instruction{}
129+
for i := 0; i < len(minimalProgramInstructions); i++ {
130+
insn := minimalProgramInstructions[i]
131+
fmt.Printf("\tattempting to remove instruction: %d, removed: %d \r", i, removed)
132+
if !protobuf.Equal(insn, noop) {
133+
minimalModified = append(minimalModified, insn)
134+
continue
135+
}
136+
137+
candidateProgram := []*pb.Instruction{}
138+
if i != (len(minimalProgramInstructions) - 1) {
139+
candidateProgram = append(minimalModified, minimalProgramInstructions[i+1:]...)
140+
} else {
141+
candidateProgram = minimalModified
142+
}
143+
144+
// If bug is no longer present then the instruction cannot be removed
145+
if !bugCheckFunction(&pb.Program{
146+
Functions: []*pb.Functions{
147+
{
148+
Instructions: candidateProgram,
149+
},
150+
},
151+
Maps: program.Maps,
152+
}) {
153+
minimalModified = append(minimalModified, insn)
154+
} else {
155+
// if the bug is present without the instruction then it can
156+
// be removed from the program.
157+
removed += 1
158+
}
159+
}
160+
fmt.Println()
161+
return removed != 0, minimalModified
162+
}
163+
164+
changesDone := true
165+
iteration := 0
166+
for changesDone {
167+
fmt.Printf("> iteration: %d of minimizer\n", iteration)
168+
changesDone = false
169+
170+
// Noop instructions.
171+
changes := phase1()
172+
changesDone = changesDone || changes
173+
174+
// Reduce jumps.
175+
changes = phase2()
176+
changesDone = changesDone || changes
177+
178+
// Remove noops.
179+
changes, minInstructions := phase3()
180+
181+
changesDone = changesDone || changes
182+
minimalProgramInstructions = minInstructions
183+
minimalProgram.Functions[0].Instructions = minimalProgramInstructions
184+
185+
iteration += 1
186+
}
46187

188+
return minimalProgram, nil
189+
190+
}
191+
192+
// GeneratePoc generates a c program that can be used to reproduce fuzzer
193+
// test cases.
194+
func GeneratePoc(program *pb.Program, bugCheckFunction func(*pb.Program) bool, footerSize int) error {
195+
minimizedProgram, err := Minimizer(program, bugCheckFunction, footerSize)
196+
if err != nil {
197+
return err
198+
}
199+
return writeJsonProgram(minimizedProgram)
47200
}

‎pkg/units/control.go‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -178,7 +178,6 @@ func (cu *Control) runEbpf(prog *epb.Program) error {
178178
ok := cu.strat.OnExecuteDone(cu.ffi, exRes)
179179
if !ok {
180180
fmt.Println("Program produced unexpected results")
181-
ebpf.GeneratePoc(prog)
182181
}
183182
return nil
184183
}

‎pkg/units/ffi.go‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -165,7 +165,9 @@ func (e *FFI) ValidateEbpfProgram(encodedProgram *fpb.EncodedProgram) (*fpb.Vali
165165
if err != nil {
166166
return nil, err
167167
}
168-
e.MetricsUnit.RecordVerificationResults(res)
168+
if e.MetricsUnit != nil {
169+
e.MetricsUnit.RecordVerificationResults(res)
170+
}
169171
return res, nil
170172
}
171173

‎tools/BUILD‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,24 @@ package(
2020
],
2121
)
2222

23+
go_binary(
24+
name = "minimizer",
25+
srcs = ["minimizer.go"],
26+
gc_linkopts = [
27+
"-linkmode=external",
28+
"-extldflags=-static",
29+
],
30+
static = "on",
31+
deps = [
32+
"//pkg/ebpf",
33+
"//pkg/units",
34+
"//proto:ebpf_go_proto",
35+
"//proto:ffi_go_proto",
36+
"@com_github_golang_protobuf//jsonpb",
37+
"@com_github_golang_protobuf//proto",
38+
],
39+
)
40+
2341
go_binary(
2442
name = "ffi",
2543
srcs = ["ffi.go"],

‎tools/minimizer.go‎

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
package main
2+
3+
import (
4+
"buzzer/pkg/ebpf/ebpf"
5+
"buzzer/pkg/units/units"
6+
epb "buzzer/proto/ebpf_go_proto"
7+
fpb "buzzer/proto/ffi_go_proto"
8+
"flag"
9+
"fmt"
10+
jsonpb "github.com/golang/protobuf/jsonpb"
11+
"os"
12+
"strings"
13+
)
14+
15+
var (
16+
samplePath = flag.String("sample", "", "JSON sample of the ebpf program to minimize")
17+
)
18+
19+
func main() {
20+
flag.Parse()
21+
fmt.Println("hello world!")
22+
23+
ffi := &units.FFI{
24+
MetricsUnit: nil,
25+
}
26+
27+
encodedProto, err := os.ReadFile(*samplePath)
28+
29+
if err != nil {
30+
fmt.Printf("error reading file: %v\n")
31+
return
32+
}
33+
34+
program := &epb.Program{}
35+
err = jsonpb.UnmarshalString(string(encodedProto), program)
36+
if err != nil {
37+
fmt.Println(err)
38+
return
39+
}
40+
err = ebpf.GeneratePoc(program, func(prog *epb.Program) bool {
41+
encodedProg, encodedFuncInfo, err := ebpf.EncodeInstructions(prog)
42+
43+
if err != nil {
44+
fmt.Printf("Encoding error: %v\n", err)
45+
return false
46+
}
47+
48+
encodedProgram := &fpb.EncodedProgram{
49+
Program: encodedProg,
50+
Btf: prog.Btf,
51+
Function: encodedFuncInfo,
52+
Maps: prog.Maps,
53+
}
54+
validationResult, err := ffi.ValidateEbpfProgram(encodedProgram)
55+
defer func() {
56+
ffi.CleanFdArray(validationResult.FdArrayAddr, len(prog.Maps))
57+
}()
58+
ebpf.LatestLogMinimizer = validationResult.VerifierLog
59+
60+
if !validationResult.IsValid {
61+
return false
62+
}
63+
64+
defer func() {
65+
ffi.CloseFD(int(validationResult.ProgramFd))
66+
}()
67+
68+
return strings.Contains(validationResult.VerifierLog, "verifier bug")
69+
70+
})
71+
if err != nil {
72+
fmt.Printf("%v", err)
73+
}
74+
}

0 commit comments

Comments
 (0)