Metering does not catch all functions that exceed limit

[AdamSLevy]

Describe the bug

A function may exceed a limit set by the wasmer_middleware_common::metering::Metering by an arbitrary amount so long as it avoids the following instructions.

Operator::Br
Operator::BrTable
Operator::BrIf
Operator::Call
Operator::CallIndirect

Of course the points used may be checked after the fact, but this is not obvious to users of the library.

Moreover, the point of metering in many cases is to prevent execution beyond a certain point. The current metering implementation only checks if the limit was exceeded after a code segment has completed, but not even at the end of a function.

There are two issues that may be addressed separately but are related:

• Functions that have exceeded the limit may end without a limit check occurring. Causing implementations to not necessarily notice that a limit was exceeded.
• Functions may exceed limits to any amount so long as they avoid the above listed instructions that cause a check. A function could be crafted to cause a DOS attack against a metered runtime.

The first issue can probably simply be resolved by adding any operators that may end a function like Operator::End and Operator::Return to the list of operators that cause a limit check.

The second issue is more complex because it requires that the cost of a code segment be statically known so that a check can be inserted ahead of the code segment, but since we are streaming the code the current implementation doesn't know that cost at that time.

I think this can be addressed by allowing the feed_event function to cache Events in the Metering struct until a complete code segment is parsed and the cost is known. Then the cost can be added and the limit checked before pushing the cached operations and starting to parse the next code segment. When Event::InternalEvent::FunctionEnd is received, the last code segment can be flushed and pushed onto the EventSink.

Steps to reproduce

I believe this behavior is actually known to the devs because the middleware-core-tests tests actually account for it.

In this test, the limit is set at 100, and the points used is 109. In this case the function did hit an operator that caused a limit check. Nine extra operations isn't so bad, but a function could make many more without a limit check occurring

wasmer/lib/middleware-common-tests/src/lib.rs

Lines 124 to 150 in d5f25aa

	fn test_traps_after_costly_call() {
	use wasmer_runtime_core::error::RuntimeError;
	let wasm_binary = wat2wasm(WAT).unwrap();
	let limit = 100u64;
	let module = compile_with(&wasm_binary, &get_compiler(limit)).unwrap();
	let import_object = imports! {};
	let mut instance = module.instantiate(&import_object).unwrap();
	set_points_used(&mut instance, 0u64);
	let add_to: Func<(i32, i32), i32> = instance.func("add_to").unwrap();
	let result = add_to.call(10_000_000, 4);
	let err = result.unwrap_err();
	match err {
	RuntimeError::Error { data } => {
	assert!(data.downcast_ref::<ExecutionLimitExceededError>().is_some());
	}
	_ => unreachable!(),
	}
	// verify it used the correct number of points
	assert_eq!(get_points_used(&instance), 109); // Used points will be slightly more than `limit` because of the way we do gas checking.
	}

A better example is this test case. This is expected to consume 74 points, so if we set the limit at 73 we should expect it to exceed the limit check and return an error during execution, but you will see that the test still passes.

wasmer/lib/middleware-common-tests/src/lib.rs

Lines 101 to 121 in d5f25aa

	fn test_points_reduced_after_call() {
	let wasm_binary = wat2wasm(WAT).unwrap();
	let limit = 100u64;
	let module = compile_with(&wasm_binary, &get_compiler(limit)).unwrap();
	let import_object = imports! {};
	let mut instance = module.instantiate(&import_object).unwrap();
	set_points_used(&mut instance, 0u64);
	let add_to: Func<(i32, i32), i32> = instance.func("add_to").unwrap();
	let value = add_to.call(3, 4).unwrap();
	// verify it returns the correct value
	assert_eq!(value, 7);
	// verify it used the correct number of points
	assert_eq!(get_points_used(&instance), 74);
	}

I am working on a better example that goes over the limit by more than one point.

Expected behavior

A function should return an ExecutionLimitExceededError if the limit is exceeded even by one point. Ideally a function should not proceed beyond its execution limit.

Actual behavior

Some functions may return with the limit exceeded but not return an error. Even functions that return an ExecutionLimitExceededError will have likely performed execution beyond their limit.

Additional context

I am interested in rewriting the feed_event function to implement my suggested approach above. Please let me know about any issues that you see with that approach.

[AdamSLevy]

I have attempted to implement my proposed approach but I am running into issues with lifetimes and the feed_event function. I'm not sure if it is possible to cache Event's in the Metering struct like I am trying to do. I am new to rust so I am still learning the right way to approach these problems.

If any of the devs or others who value accurate metering would be willing to take a look and suggest an approach I would greatly appreciate it.

https://github.com/AdamSLevy/wasmer/blob/MeteringImproved/lib/middleware-common/src/metering.rs

[ethanfrey]

I came across this issue when doing tests with a trivial (4 points, add two i32) wasm call.
It never errored with metering regardless of limit or points used.
All non-trivial code I wrote seem to hit limits, so I didn't think too much more about the issue, "well, exceed by 4 points on return, close enough".

Thank you for digging into this issue deeper. As to a sample test, just a lot of multiplies and adds with some variables, should produce wasm that can use eg. 100 points and never trigger a check.

[AdamSLevy]

An issue that I'm having with my re-write, is that the lifetime of the Event passed into feed_event is such that it cannot be saved into the Metering struct to be pushed onto the EventSink on some later call. I think this is a limitation of the MiddlewareChain design and prevents middleware chains from being able to observe more than one Event at a time. To allow the approach that I suggested above, and attempted to implement, I believe some rework of the feed_event trait and runtime_core::MiddlewareChain struct will be required. I also considered doing this in two passes with two middleware chains, but again, middleware chains pass each Event along one at a time. They don't each receive the full set of Events before they are all passed to the next chain.

I have come up with some small but sub-optimal alternative solutions:

The smallest fix to the issue of not catching functions where the limit has been exceeded is to simply add Operator::End to the list of Events that trigger injection of limit checks. This would cause limits to be checked at the end of every function. The downside is that this does not address prevention of exceeding execution limits, only catching it after it happens. The other downside to this is that it may cause the injection of some needless limit checks. I haven't fully thought through the consequences of this.

Another simple and small, but not very elegant, solution to the issue of execution being able to exceed limits by an arbitrary amount, is to always inject checks after every X points without a check. This allows a user to define a maximum amount that the execution limit may be exceeded. The downside is that this reduces the issue, but still allows functions to be designed to exceed the limit by the hard coded maximum. Lower max values would result in more checks being injected which may degrade performance. On the other hand, the maximum could be chosen so as to avoid injection of additional checks for most code. In other words, there is some average number of points between the operations that cause checks for most code, and a recommended maximum could be 1.5 standard deviations above that, for example.

[Hywan]

Hello @AdamSLevy,

Is this issue still relevant? The problem seems solved to me as far as I can understand and try to replicate.

[Amanieu]

Closing since the issue seems to be solved.