Comments (9)
Here, I sketched a small python prototype to illustrate how it works:
import random
def generate_randomized_trace(cost_limit, cost_of):
cumulative_cost = reduce(lambda c, x: c + [c[-1] + x], cost_of, [0])
program_length = len(cost_of)
interpreter_instruction_meter = 0
jit_instruction_meter = cost_limit
cost_limit_reached = False
ip_pc = 0
while True:
if ip_pc + 1 >= program_length:
print("Program reached the end")
return
interpreter_instruction_meter += cost_of[ip_pc]
print("ip/pc={} interpreter={}/{} jit={}/{}".format(ip_pc,
interpreter_instruction_meter, cost_limit,
cumulative_cost[ip_pc + 1], jit_instruction_meter,
))
interpreter_limit_reached = cost_limit <= interpreter_instruction_meter
jit_limit_reached = jit_instruction_meter <= cumulative_cost[ip_pc + 1]
if (interpreter_limit_reached or jit_limit_reached) and not cost_limit_reached:
cost_limit_reached = True
print("Cost limit reached by interpeter={} jit={}".format(
interpreter_limit_reached, jit_limit_reached))
if random.randint(0, 100) < 20:
target_ip_pc = random.randint(0, program_length - 1)
jit_instruction_meter -= cumulative_cost[ip_pc + 1]
jit_instruction_meter += cumulative_cost[target_ip_pc]
print("Jump to ip/pc={}".format(target_ip_pc))
if cost_limit_reached:
print("JIT aborted branch")
return
else:
ip_pc = target_ip_pc
else:
ip_pc += 1
generate_randomized_trace(64, [random.randint(1, 3) for _ in range(0, 100)])
Which, for example generates the following trace:
ip/pc=0 interpreter=1/64 jit=1/64
ip/pc=1 interpreter=4/64 jit=4/64
ip/pc=2 interpreter=6/64 jit=6/64
ip/pc=3 interpreter=9/64 jit=9/64
ip/pc=4 interpreter=11/64 jit=11/64
Jump to ip/pc=8
ip/pc=8 interpreter=12/64 jit=17/69
Jump to ip/pc=63
ip/pc=63 interpreter=14/64 jit=128/178
ip/pc=64 interpreter=17/64 jit=131/178
Jump to ip/pc=89
ip/pc=89 interpreter=18/64 jit=177/223
ip/pc=90 interpreter=19/64 jit=178/223
ip/pc=91 interpreter=20/64 jit=179/223
ip/pc=92 interpreter=22/64 jit=181/223
Jump to ip/pc=45
ip/pc=45 interpreter=23/64 jit=90/131
ip/pc=46 interpreter=25/64 jit=92/131
ip/pc=47 interpreter=26/64 jit=93/131
ip/pc=48 interpreter=28/64 jit=95/131
Jump to ip/pc=69
ip/pc=69 interpreter=29/64 jit=142/177
ip/pc=70 interpreter=30/64 jit=143/177
ip/pc=71 interpreter=32/64 jit=145/177
ip/pc=72 interpreter=33/64 jit=146/177
Jump to ip/pc=29
ip/pc=29 interpreter=34/64 jit=59/89
ip/pc=30 interpreter=36/64 jit=61/89
ip/pc=31 interpreter=37/64 jit=62/89
ip/pc=32 interpreter=38/64 jit=63/89
ip/pc=33 interpreter=39/64 jit=64/89
ip/pc=34 interpreter=40/64 jit=65/89
ip/pc=35 interpreter=43/64 jit=68/89
ip/pc=36 interpreter=46/64 jit=71/89
ip/pc=37 interpreter=49/64 jit=74/89
ip/pc=38 interpreter=50/64 jit=75/89
ip/pc=39 interpreter=53/64 jit=78/89
ip/pc=40 interpreter=54/64 jit=79/89
ip/pc=41 interpreter=57/64 jit=82/89
Jump to ip/pc=47
ip/pc=47 interpreter=58/64 jit=93/99
ip/pc=48 interpreter=60/64 jit=95/99
ip/pc=49 interpreter=63/64 jit=98/99
ip/pc=50 interpreter=64/64 jit=99/99
Cost limit reached by interpeter=True jit=True
ip/pc=51 interpreter=67/64 jit=102/99
ip/pc=52 interpreter=68/64 jit=103/99
ip/pc=53 interpreter=71/64 jit=106/99
ip/pc=54 interpreter=73/64 jit=108/99
ip/pc=55 interpreter=76/64 jit=111/99
Jump to ip/pc=75
JIT aborted branch
So the only difference to how it currently is, is that cumulative_cost
is not the identity function anymore, but the lookup can happen at compile time.
from rbpf.
Thankfully, static analysis is always possible as there are no arbitrary code jumps in eBPF - jumps are always to an inlined offset.
from rbpf.
@jackcmay @Lichtso , for the reason that static analysis may be expensive in the malicious or even non-malicious scenario, I think the above approach may be a good way to perform "intermediate JIT" in the non-uniform opcode cost case.
The static analysis could then only be applied to programs that live for a long time in the executor cache, as a one-time cost.
Rather than eagerly JITing+statically analysing every program.
So the compilation hierarchy:
- Interpreted
- Inline JIT (above approach)
- Static analysis "full" compilation
from rbpf.
Even if the static analysis is expensive, it would probably be possible to compile asynchronously in a background thread, and silently replace the JITed binary by acquiring a write lock to the cache.
from rbpf.
Thankfully, static analysis is always possible as there are no arbitrary code jumps in eBPF - jumps are always to an inlined offset.
Unfortunately, we have ebpf::CALL_REG
(callx
instruction) which is a dynamic (unpredictable) jump.
May I know if a non-uniform opcode compute unit cost table is on the horizon?
Yes, I don't see why not. In fact it is a lot simpler than you think and works with the current approach out-of-the-box.
We only have to add an explicit cumulative cost table instead of using the pc directly. There is no need to emit any extra x86 instructions for more expensive BPF instructions.
from rbpf.
Yep, that integral trick is very elegant. Still makes me worried about long straight-line programs.
from rbpf.
Still makes me worried about long straight-line programs.
We could emit phony branches if we detect long linear runs, but these are not particularly useful anyway.
And, yes I am aware that these programs are still turing complete and things like the movfuscator exist, but they also prove how limited this approach is as it bloats the program size tremendously.
Edit: Just remembered that the last return / exit counts as a branch too, so that would check if the program did run too long.
from rbpf.
@Lichtso my worry is not the detection per-se but rather to catch such programs in the act so they don't run for say 100ms rather than say a target 10ms.
There's actually a separate issue involved, which is that if the program throws an error or panics after it was supposed to have run out of budget, then it may return a different return type. I guess this wouldn't be a problem if every error or branch into an error also first checks the compute meter (perhaps already subsumed under the conditions for returning)
from rbpf.
There's actually a separate issue involved, which is that if the program throws an error or panics after it was supposed to have run out of budget, then it may return a different return type
Interesting idea, might not be covered so far, but would have to write a test case for that.
This is what we currently have:
Line 436 in 42ca251
from rbpf.
Related Issues (20)
- The new ELF parser should use checked instead of saturating arithmetic
- elf: retrieve all dynamic metadata from the `.dynamic` table instead of requiring section headers
- JitCompiler::new() uses unwrap()
- Read only sections can overlap with the stack
- eBPF Standardization HOT 2
- Call target labels are not resolved in v0.2.38 HOT 4
- 32bit target support HOT 2
- ExceededMaxInstructions error message is confusing HOT 1
- Only require winapi on Windows
- git clone and cargo build gives error HOT 3
- elf_parser fails loading a valid ELF file HOT 8
- Call instruction transfers control to incorrect address HOT 4
- RBPF is killed by the OS while running a program HOT 2
- make btf instruction class an enum
- Attempt to negate with overflow in disassembler
- Warnings when compiling on macOS Arm
- Removing check SHIFT immediate number from verifier HOT 2
- assembler: register inconsistency HOT 3
- Interpreter LD_DW_IMM: add `!sbpf_version.disable_lddw()` checking
- type casting of rbpf HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from rbpf.