Online Pen Testing
summary
Defines an online “pen testing” model where testing reduces an option’s value by threshold theta and passing reveals only residual value; proves a universal log n lower bound (exponential distribution shows any test leaves expected remaining value O(1) while max is Θ(log n)). Gives a matching log n upper bound via testing all items at a random powers-of-two threshold and accepting first pass, and characterizes prophet/secretary variants (best case improves to Θ(log n / log log n)).
AI-written summary · about
chapters (8)
- 0:00The pen testing problem
- 2:47Formal problem setup
- 5:20Related literature
- 8:06Setting parameters
- 10:43Complexity and lower bounds
- 13:25Algorithmic approach
- 16:14Generalized results
- 19:50Conclusion and future work
related talks
43mThe Sad Tale of Etaoin ShrdLu and the Danger of Automated Pen Tests
35mBreaking Boundaries with Adversarial Testing
12mConfessions of a reformed pentester
50mTime Trial: Racing Towards Practical Timing Attacks
33mWorking with penetration testers as a developer
32mBlack box side-channel leakage verification using statistical approach
01h 08mTutorial: Security
33mYes, There is an Oblivious RAM Lower Bound!