burtonqin/lockbud

Statically detect Rust deadlocks bugs

TSE Code and Data Release

Code

Code contains Double-Lock, Conflicting-Lock-Order, Atomicity-Violation, Use-After-Free, Invalid-Free Detectors

and Panic Location Detector.

Data

Data contains BugStudy.xlsx, which records all the study results, and BugReport.xlsx, which records all the experimental results,

lockbud's Issues

Add github action

Add a github action yml configuration, so that it can be automatically checked after each code commit.

Keep up to date with rustc

Improve the precision of automata

• To locate the Source of the LockGuard:
• 1. LockGuard to &Lock
• 2. &Lock to LockSrc
• lg_from_re(LG, RE) :-
• LG=call(move RE,...),Type(RE) contains Type(LG).
• re_from_re(RE, RE1) :-
• RE=call(move RE1,...), Type(RE) shares with Type(RE1).
• re_from_re(RE, RE1) :-
• RE=move RE1, Type(RE)=Type(REq1).
• lg_from_lg(LG, LG1) :-
• LG=move LG1,Type(LG)=Type(LG1).
• lg_from_lr(LG, LR) :-
• LG=call(move LR), Type(LG) shares with Type(LR), + Type(LG) contains std.
• re_from_lr(RE, LR) :-
• RE=call(move LR), Type(LG) shares with Type(LR), Type(LG) contains std.
• Mutex.lock(), Arc, Foo.Field, ..., (TODO)

FPs with RwLock::read_recursive

parking_lot provides an API called RwLock::read_recursive, which allows recursively acquiring read locks.
This kind of FPs is found in https://github.com/Conflux-Chain/conflux-rust

A possible solution is to track the gen places of parking_lot read locks.
If it is read_recursive, then do not report double-read-lock bugs.

Keep up to date with rustc?

I want to use the latest nightly release. I wonder if lockbud compiling successfully in the latest nightly means ok to use?

Prepare code and data release of TSE

1. Move all the checkers to master branch
2. Move the original double-lock and conflicting-lock detectors to the lock branch
3. Create a Data directory for experimental data release

Integration in Clippy ?

Great work, I'm wondering if it could be directly integrated into clippy.

Do you think it would be possible ?
If yes, does it sound reasonable to have it as a general mechanism, for example having #[clippy::forbid_call(self, ::crate::module::my_fn)] at the function definition ?

FPs caused by passing LockGuard directly as parameters

This is the case for crate blocking and many other repos.

Update the callgraph generation with an ICSE'20 paper

Paper:
Is Rust Used Safely by Software Developers?
https://arxiv.org/ftp/arxiv/papers/2007/2007.00752.pdf
Code:
https://github.com/ananevans/icse2020/

On Mac OS: `lockbud/cargo_dir.txt: No such file or directory`

lockbud % ./detect.sh toys/conflict-inter
    Finished dev [unoptimized + debuginfo] target(s) in 0.06s
realpath: /Users/user/Documents/Code/lockbud/cargo_dir.txt: No such file or directory
usage: touch [-A [-][[hh]mm]SS] [-achm] [-r file] [-t [[CC]YY]MMDDhhmm[.SS]]
       [-d YYYY-MM-DDThh:mm:SS[.frac][tz]] file ...
./detect.sh: line 41: $cargo_dir_file: ambiguous redirect
./detect.sh: line 44: ${cargo_dir_file}: ambiguous redirect

run ./detect.sh failed

error: failed to run rustc to learn about target-specific information

Caused by:
process didn't exit successfully: /home/luoyangze.ptrl/rust/lockbud/target/debug/lockbud rustc - --crate-name ___ --print=file-names --crate-type bin --crate-type rlib --crate-type dylib --crate-type cdylib --crate-type staticlib --crate-type proc-macro --print=sysroot --print=cfg (exit status: 127)
--- stderr
/home/luoyangze.ptrl/rust/lockbud/target/debug/lockbud: error while loading shared libraries: librustc_driver-281a9b3e4c740b61.so: cannot open shared object file: No such file or directory

FPs in condvar deadlock detector when the two locks are the same

This is the case in crate blocking and many other crates.

why use the "instance" rather than implementing a block visitor to build the callgraph?

Linking Error

Hi,
I tried installing the detector as described in the Readme using cargo install --path . within a docker container running the rust:latest image.
Unfortunately the following error occurs.

error: linking with `cc` failed: exit code: 1
  |
  = note: "cc" "-Wl,--as-needed" "-Wl,-z,noexecstack" "-m64" "-Wl,--eh-frame-hdr" "-L" "/usr/local/rustup/toolchains/nightly-2021-01-13-x86_64-unknown-linux-gnu/lib/rustlib/x86_64-unknown-linux-gnu/lib" "/workspace/target/release/deps/rust_lock_bug_detector-c90916a71681a1c3.rust_lock_bug_detector.3zkkwcmj-cgu.0.rcgu.o" "/workspace/target/release/deps/rust_lock_bug_detector-c90916a71681a1c3.rust_lock_bug_detector.3zkkwcmj-cgu.1.rcgu.o" "/workspace/target/release/deps/rust_lock_bug_detector-c90916a71681a1c3.rust_lock_bug_detector.3zkkwcmj-cgu.10.rcgu.o" "/workspace/target/release/deps/rust_lock_bug_detector-c90916a71681a1c3.rust_lock_bug_detector.3zkkwcmj-cgu.11.rcgu.o" "/workspace/target/release/deps/rust_lock_bug_detector-c90916a71681a1c3.rust_lock_bug_detector.3zkkwcmj-cgu.12.rcgu.o" "/workspace/target/release/deps/rust_lock_bug_detector-c90916a71681a1c3.rust_lock_bug_detector.3zkkwcmj-cgu.13.rcgu.o" "/workspace/target/release/deps/rust_lock_bug_detector-c90916a71681a1c3.rust_lock_bug_detector.3zkkwcmj-cgu.14.rcgu.o" "/workspace/target/release/deps/rust_lock_bug_detector-c90916a71681a1c3.rust_lock_bug_detector.3zkkwcmj-cgu.15.rcgu.o" "/workspace/target/release/deps/rust_lock_bug_detector-c90916a71681a1c3.rust_lock_bug_detector.3zkkwcmj-cgu.2.rcgu.o" "/workspace/target/release/deps/rust_lock_bug_detector-c90916a71681a1c3.rust_lock_bug_detector.3zkkwcmj-cgu.3.rcgu.o" "/workspace/target/release/deps/rust_lock_bug_detector-c90916a71681a1c3.rust_lock_bug_detector.3zkkwcmj-cgu.4.rcgu.o" "/workspace/target/release/deps/rust_lock_bug_detector-c90916a71681a1c3.rust_lock_bug_detector.3zkkwcmj-cgu.5.rcgu.o" "/workspace/target/release/deps/rust_lock_bug_detector-c90916a71681a1c3.rust_lock_bug_detector.3zkkwcmj-cgu.6.rcgu.o" "/workspace/target/release/deps/rust_lock_bug_detector-c90916a71681a1c3.rust_lock_bug_detector.3zkkwcmj-cgu.7.rcgu.o" "/workspace/target/release/deps/rust_lock_bug_detector-c90916a71681a1c3.rust_lock_bug_detector.3zkkwcmj-cgu.8.rcgu.o" "/workspace/target/release/deps/rust_lock_bug_detector-c90916a71681a1c3.rust_lock_bug_detector.3zkkwcmj-cgu.9.rcgu.o" "-o" "/workspace/target/release/deps/rust_lock_bug_detector-c90916a71681a1c3" "-Wl,--gc-sections" "-pie" "-Wl,-zrelro" "-Wl,-znow" "-Wl,-O1" "-nodefaultlibs" "-L" "/workspace/target/release/deps" "-L" "/usr/local/rustup/toolchains/nightly-2021-01-13-x86_64-unknown-linux-gnu/lib/rustlib/x86_64-unknown-linux-gnu/lib" "-L" "/usr/local/rustup/toolchains/nightly-2021-01-13-x86_64-unknown-linux-gnu/lib/rustlib/x86_64-unknown-linux-gnu/lib" "-lrustc_driver-28f4036956f26eb4" "-Wl,--start-group" "-L" "/usr/local/rustup/toolchains/nightly-2021-01-13-x86_64-unknown-linux-gnu/lib/rustlib/x86_64-unknown-linux-gnu/lib" "-lstd-8ca495943bae7405" "-Wl,--end-group" "-Wl,-Bstatic" "/usr/local/rustup/toolchains/nightly-2021-01-13-x86_64-unknown-linux-gnu/lib/rustlib/x86_64-unknown-linux-gnu/lib/libcompiler_builtins-ea377e9224b11a8a.rlib" "-Wl,-Bdynamic" "-lLLVM-11-rust-1.51.0-nightly" "-lgcc_s" "-lutil" "-lrt" "-lpthread" "-lm" "-ldl" "-lc"
  = note: /usr/bin/ld: cannot find -lLLVM-11-rust-1.51.0-nightly
          collect2: error: ld returned 1 exit status

Maybe link to specific examples of bugs found?

Something like https://github.com/rust-lang/miri#bugs-found-by-miri

FPs caused by the same lock in a loop or recursive function

When a lock is locked in a loop or recursive function, it may report FPs, e.g., https://github.com/Yoric/timer.rs.

For a loop: the current static analysis cannot determine if a path (acquiring the lock again when the lock in the previous iteration is not released) can be executed or not (possibly not). It may require some techniques like SMT solver to provide a precise result. For now just omit this case.

For a recursive function: the current static analysis mistakenly assumes that the locks used in the caller and the callee alias with each other, which is not for most of the cases. For example, foo(a) calls foo(a.child), where a and a.child cannot alias with each other semantically, but it is hard for the alias analysis to learn this. Therefore, we just omit this case.

The above two cases share the same symptom: the first and the second lock share the same span. So we just filter out this case in the deadlock detection.

[Feature Request] Make it a cargo subcommand

Thank you for building such a powerful tool.

Could you deploy it as a cargo subcommand in the future?

So that we can easily check our own project like this:

cargo detect-lock-bug

And it's better to give a human-readable output by default.

Support for Tokio::sync primitives

Thank you very much for this tool, it has helped me and my team several times to find critical deadlocks 👏

The only missing part is having support for the primitives from Tokio::sync such as: RwLock & Mutex.

Is it even possible to track usage of asynchronous locks in a similar fashion?

If yes, I would be happy to help and contribute as it would be a game changer for my current usage of Rust.

Detect Rayon deadlocks

Rayon has this footgun for lock usage where it can deadlock if both of the following conditions are true:

1. Lock L is held while calling into Rayon (e.g. calling rayon::join while holding a mutex).
2. Lock L is accessed from within Rayon tasks (e.g. calling mutex.lock() within par_iter).

Deadlocks can occur in multiple ways: if the first thread that is holding the lock calls into Rayon and steals some of the jobs of type (2) which require the lock, then those jobs will not complete because of the circular dependency (they are waiting for the thread to release the lock, but the thread is waiting for them to complete because it is waiting for the Rayon call to return). There's a similar variant if the thread holding the lock is itself a Rayon thread, in which case the deadlock occurs because the thread tries to re-lock the lock it already holds.

How could lockbud help? It would be prone to false positives, but it could detect any calls to Rayon functions that occur while holding a Mutex/RwLock. I think this is similar to detecting double-locking.

Unfortunately it seems that a deadlock-avoiding mutex for Rayon is not likely to be implemented any time soon. The naive approach of yielding when locking fails does not work because there is no "task" that can be yielded to which will unblock execution – we need the current task to finish to return control to the caller (see rayon-rs/rayon#592 (comment)). Unlike in async code, there is no way to interrupt a Rayon task while it is running, because it is just an ordinary function. This suggests it also wouldn't be feasible to port tokio::sync::Mutex which uses wakers and other futures-specific features to work around this problem in the async context (see https://github.com/tokio-rs/tokio/blob/2400769b54fd31186b07bfbec277e846e8d64c16/tokio/src/sync/batch_semaphore.rs#L2-L17).