Introduction

Programming languages can have unexpected flaws that can go undiscovered for years. In this post, I discuss how I developed a fuzzer for Lua 5.2, which led me to discover a bug in its arithmetic operations. Interestingly, this bug was not only present in Lua 5.2, but also in its previous versions and in Luau: a Lua dialect used by Roblox.

What are fuzzers?

Fuzzers are automated tools that generate random inputs to an algorithm using mutators. A mutator is a function that generates mutated inputs to pass to a function.

For example, an arithmetic mutator may generate high-entropy inputs to pass to an arithmetic operator, and the fuzzer will evaluate all of these mutated operations’ using Lua’s implementation of arithmetic and compares the results to the expected results. If the results are different, then the fuzzer has found a bug in Lua’s arithmetic, essentially some operation and its inputs that evaluate differently in Lua compared to other languages.

Why fuzz Lua?

Fuzzing a programming language can give some important insight on how the behavior of one language differs from another.

Whilst I was fuzzing Lua, I had one intention: find bugs to abuse in my obfuscator, and that’s exactly what I did.

Developing the fuzzer

Funny enough, I didn’t really fuzz past this point, as the bug I found was actually in the first thing I even checked, which was Lua’s arithmetic.

Setting up the fuzzer

I started by creating a simple fuzzer in Rust that implements the logic of Lua’s arithmetic.

/// Returns a list of binary operations that failed the fuzzer's test.
fn test_arithmetic() -> Vec<BinaryOperation> {
    let mut mutator = ArithmeticMutator::new();
    let mut fuzzer = ArithmeticFuzzer::new(&mut mutator);

    fuzzer.fuzz()
}

What I found

After running my fuzzer for a while, I uncovered thousands of operations that were broken, all of them were using modulus.

To test this, I simply ran the following piece of code in Luau, then in Python:

print(2598868282423058066078711118172537907981582336 % 11)

And here is a portion of the thousands of bad equations that were generated:

[Lua] 11625296524877901313552836338555115842524992174759245762799314865823454737134082322607118479333893557510482617108410418276276083556761557979152241410989827469787801268330146880992539490342953843935496123214386113636574510693039686081586344878436512644321189691366012007991559318463840256.000000 % 37 = -2113178124542660985409359139666066426075389304144486088511842836106695610226899437897669023550628751578697579973028514715529390238010742149002155913851758307633546735996020336674926070705705764212096931632844753616592113171006246955353587595068145905958154323590951993344.000000	[Real] 12.000000
[Lua] 19587574696743470491109528437910405120.000000 % 25 = -2361183241434822606848.000000	[Real] 20.000000
[Lua] 29124623405542683629203969998234524319744.000000 % 165 = -4835703278458516698824704.000000	[Real] 39.000000
[Lua] 52034810407905050370446478970563931595614430894399149000097832818115782495081592531324937909623082425316687873930055417636292919942432222570281084217186987295113216.000000 % 55 = -6393341031047152089869511126616404594173128996177860916959553453312761321102879990006386899074031556935325554936640763689877454191182408307282280448.000000	[Real] 31.000000
[Lua] 90833860569224543364959059469427712319696249609046338169156347814561822936902476263972191455611231194664137966313896599255037739506189005494095946178363392.000000 % 11 = -11908525658859223294760121268437066290850060053501019099651935423375594096449911575776314174894302258147533153997065059263030913083222523904.000000	[Real] 9.000000
[Lua] 869766097502933285259921095807500071931476424141238621591216207378714360962071710546519204220935346006955100424085769941488184284803837820575361075838898366869795192202796145666740161050325286912.000000 % 11 = -129672361527531029953512745740348785969138944757576153124864291552832900356653379574990845279596993571506183956603149661949848471106617978371464838566061365220661931356297172615168.000000	[Real] 2.000000
[Lua] 1235972174627548644676611342336.000000 % 5 = -140737488355328.000000	[Real] 1.000000
[Lua] 2305979831916348673362549286216430734681186252811570276731156760557231404783288634389171559657092887002220690887005153744909885842963911770524915605700608.000000 % 21 = -372141426839350727961253789638658321589064376671906846864122981980487315514059736743009817965446945567110411062408283101969716033850703872.000000	[Real] 4.000000
[Lua] 18101297804411644504296028502343100577788106559574175768271338699555572205874144924925952.000000 % 135 = -3533694129556768659166595001485837031654967793751237916243212402585239552.000000	[Real] 122.000000
[Lua] 10960406665224913625632264332656639691959479145590927483566404157099480967020544.000000 % 79 = -1645504557321206042154969182557350504982735865633579863348609024.000000	[Real] 16.000000
[Lua] 670538596544958570502968424721255824704216994454990617486850606997842008084396349990497353749727429340943148839452930003635453756079016826661582378721053472000721750542236605722530877583535555934202192380188279094945032626296082298328119809186725888.000000 % 5 = -99361157907245371849534687261600163536440705095468583112899330433667260971928120725176218165033374588831214764616388685194981122823348121052434385602635592909085118465334393955216978280422300468816831948397854000057142198644227702784.000000	[Real] 3.000000
[Lua] 2248812680652649736889618208391168.000000 % 11 = -288230376151711744.000000	[Real] 5.000000

I was surprised to see that modulus was broken, as it’s a very simple operation to implement. I decided to look into the implementation of modulus in Lua.

Lua’s implementation of modulus

Lua’s implementation of floating point modulus is defined as the following:

(x - (floor(x / y) * y))

This equation is not wrong, but it will not always work on a modern CPU. This is because in order to represent numbers with decimals, we use floats. These floats have a specific encoding that follows the IEEE 754 standard. This standard defines how floats are encoded, and how they are represented in memory.

The problem with this equation is that it assumes that the result of floor(x / y) is exact, which is not always the case. This is because floats have a limited precision, and the result of floor(x / y) may not be exact. This is a problem, as the result of floor(x / y) is multiplied by y, which will cause the result to be off by a small amount, which may be greater than or equal to x, causing the subtraction and overall result of modulus to be 0, or even negative, which is obviously wrong.

Fixing the bug

As I’ve noted, Lua has actually fixed this bug since Lua 5.3, intentional or not.

This was done by simply switching to libc’s implementation of floating point modulus, which is fmod(x, y), which will give the correct result to a limited precision, but never negative.

One must also think about the performance of this operation. The equation Lua uses is faster than fmod(x, y), but it’s not always correct.

Conclusion

This bug was a very interesting find and fun piece of research. I even used it in my obfuscator to prevent static analysis, which I’ll be writing about in a future post.

I hope you enjoyed this post, and I hope you learned something new. If you have any questions, feel free to reach out to me at our Discord server.