8 ms·
I really like the development of all the sanitizers we got in the last decade or so. I only wish that more could be done at compile time as opposed to these run
by adrianN 7y ago
I really like the development of all the sanitizers we got in the last decade or so. I only wish that more could be done at compile time as opposed to these runtime checks.
- lallysingh 7y agoSure, just look at the languages that have more stringent type systems.
- adrianN 7y agoThey don't really help me make the mountains of C we have in the world less buggy.
- lallysingh 7y agoC code doesn't have enough information in it to do a whole lot of mechanical analysis. Runtime analysis of its behavior is what you've got.
- nickpsecurity 7y agoHave you never heard of program analysis for security? Genuine question. RVI, the Mayhem developers, and many others would strongly disagree with you: https://runtimeverification.com/match/1.0-SNAPSHOT/docs/benchmark/ https://runtimeverification.com/match/1.0-SNAPSHOT/docs/benc... https://spectrum.ieee.org/computing/software/mayhem-the-machine-that-finds-software-vulnerabilities-then-patches-them https://spectrum.ieee.org/computing/software/mayhem-the-mach... The field evidence would support their position, too. Your claim about C is true just enough to encourage people to not use it if they want to get more out of program analysis. Yet, current tools make up for it enough to find most or all bugs in benchmarks with Mayhem fixing them, too. The only problem is that almost nobody that cares about FOSS security is working on those tools that automate it. The companies doing it end up black boxing, patenting, etc the tools that they sell for exhorbitent prices. Something like RV-Match well-integrated with repos either FOSS or just price scaled to focus on mass adoption over high profit would be a game changer. Especially if 3rd parties could use it on repos.
- lallysingh 7y agoAren't those runtime tools like I just suggested? The other ones in the 1st link are theorem provers (at least the one that I recognized, frama-c) that require a lot more than off-the-shelf C code for their inputs. You can't just run CC=my-compiler-frontend make to suddenly get better diagnostics.
- nickpsecurity 7y agoCompanies are mixing static and running analysis more than they used to. Most static analyzers look at just the code itself, build models of it, check their properties, and report the presence/absence of errors. First links were more about effectiveness on C. I just dug around in search to find you something that explains it, shows its effectiveness, and threw in a case study you might enjoy: https://www.cs.colorado.edu/~kena/classes/5828/s12/presentation-materials/blackshearsam.pdf https://www.cs.colorado.edu/~kena/classes/5828/s12/presentat... https://cacm.acm.org/magazines/2010/2/69354-a-few-billion-lines-of-code-later/fulltext https://cacm.acm.org/magazines/2010/2/69354-a-few-billion-li... Here's the main competition evaluating them so you can see criteria and current state-of-the-art: https://www.sosy-lab.org/research/pub/2019-TACAS.Automatic_Verification_of_C_and_Java_Programs_SV-COMP_2019.pdf https://www.sosy-lab.org/research/pub/2019-TACAS.Automatic_V... The provers do something similar but with more manual effort and logic-based approach. Frama-C and SPARK Ada are interesting in that they use programmer annotations plus supporting functions (eg ghost code). These are converted into logical representation (eg facts about the program), fed into logic solvers with properties intended to be proved, and success/failure maybe tells you something. Like with static analyzers, you get the results without running the program. A recent, great addition is that, if proof is too hard, the condition you didn't prove can be turned into a runtime check. You could even do that by default only proving the ones that dragged performance down too much. Flexible. The best methods are a mix. I've always advocated mixing static analyzers, dynamic analysis, fuzzing etc since each technique might spot something the other will miss. They also cover for implementation bugs each might have. That adding runtime analysis can improve effectiveness does not negate my original claim that static, non-runtime analysis of C code can tell you a lot about it and/or find a ton of bugs. I also agreed with one point you made about it not conveying enough information: these clever tools pull it off despite C lacking design attributes that would make that easier. SPARK Ada is a great example of a language designed for low-level, efficient coding and easy verification. Although, gotta give credit to Frama-C people for improving things on C side.
- KirinDave 7y agoIt does suggest we should delete it, which is pretty helpful. It's a terribly liability.
- vinceguidry 7y agoIs there even an approach to doing that? Intuition tells me that's a mathematically intractable problem.
- rhinoceraptor 7y agoYes, just probably not with a language as semantically ambiguous as C. Rust for example has guarantees against data races.
- gameswithgo 7y agoRust prevents data races at compile time. Note that data races, while a common form of race condition, is not the only kind of race condition, and Rust won't prevent the others.
- Ygg2 7y agoYou're right to an extent. I think that because of Halting problems, a number of useful properties computer could tell you about itself are limited, because they boil down to solving Halting problem. However, one way to avoid such a problem was basically settling for less accurate, but still strict subproblems. I.e. Rust doesn't stop all race conditions but solves them for a subset of data races. In other words you reject some valid programs (false positive?) in order to make sure all valid programs are really valid (false negative?).
- reirob 7y agoATS language. It compiles to C and I believe I have seen even that experimentally some kernel module was developped in it. Here some resources: The Wikipedia page: https://en.wikipedia.org/wiki/ATS_(programming_language) https://en.wikipedia.org/wiki/ATS_(programming_language) "A (Not So Gentle) Introduction To Systems Programming In ATS" by Aditya Siram at the StrangeLoop 2017: https://www.youtube.com/watch?v=zt0OQb1DBko https://www.youtube.com/watch?v=zt0OQb1DBko Introduction to ATS, a series of screen casts: https://www.youtube.com/playlist?list=PL6BIXG1a4elsauhh56i5nryB_4K4GMbFq https://www.youtube.com/playlist?list=PL6BIXG1a4elsauhh56i5n... I do not program in ATS because I am not doing anything that needs to be as efficient, so that I have the luxury to enjoy programming and learning Haskell, in the hope that by the time when I would need to write some super secure and performant program that has to run without interruption, and is used by more users than myself, well, I hope that by that time Haskell will evolve enough to allow me to write such a program. Otherwise I might end up using ATS, though honestly the syntax is so ugly.
- Zigurd 7y agoLinting for concurrency bugs is very hard. Modifying thread scheduling to make rare manifestations much less rare is much simpler.
- nickpsecurity 7y agoThe good news is it's also the golden age of static analysis right now. There's open source and commercial tools that find most of the problems. Some are scaling up on codebases the size of the Linux kernel. So, not only can you do that: it's standard practice for some developers already in and out of commercial space. Mostly commercial developers doing it that I see, though.
- sanxiyn 7y agoNote that this is a dynamic analysis, and precisely because equivalent static analysis won't scale to Linux kernel.
- nickpsecurity 7y agoIt is dynamic analysis. I don't think it's that reason. Both Saturn and Facebook's tool scaled analysis to the size of the Linux kernel. I think most developers and companies aren't using or pushing them like they could for cultural reasons. Look at the number of people that used sanitizers vs low-F.P. static analyzers even if free. The latter would've gotten them results sooner. It wasn't empirical evidence or effectiveness that led to that decision. Human factors trump technical factors in adoption decisions most of the time. http://saturn.stanford.edu/ http://saturn.stanford.edu/ Note: Linking to Saturn since it's old work by small team. I theorized big investment could achieve even more. Facebook's acquisition and continued investment with excellent results proved it. If tech and money is the limit, tell me why Google hasn't straight-up bought the companies behind RV-Match and Mayhem to turn their tech on all their code plus open-source dependencies. Even if over-priced, it might actually turn out cheaper than all the bug bounties adding up. Maybe re-sell it cheap as a service Amazon-style. The precedent is that Facebook bought one that built a scalable tool they're applying to their codebase. Then, they were nice enough to open-source it. Google, Microsoft, Apple, etc could get one, too. What's Google's excuse? They sure aren't broke or dumb. Gotta be cultural. Likewise, Microsoft built lots of internal tools. They do use at least two static analyzers: one for drivers, one for software. I heard they even ship 2nd one in VS. They don't use most of the MS Research tools, though. The reason is cultural: Operations side knows they'll keep making money regardless of crap security. Far as FOSS developers, most don't care about security. Those that do tend to follow both what takes little effort (naturally) and whats trending. The trending topics are sanitizers, fuzzers, and reproducible builds. Hence, you see them constantly instead of people learning how to build and scale program analyzers, provers, etc with much better track record. Note that I'm not against the others being built to complement the better methods. I just think, if this is rational vs emotional, you'd see most volunteer and corporate effort going to what has had highest payoff with most automation so far. For a positive example, a slice of academics are going all-in on adaptive fuzzers for that reason, too. They're getting great results like Eclipser.
- myu701 7y agoThat's the killer feature why I gave F# instead of my usual C# a chance - it 'does more for me' at compile time vs. run time. Yes, these are both much higher level than C, but if what I'm reading among other comments is correct, Rust accomplishes an equivalent improvement in compile time checks while still being a systems language.
- gameswithgo 7y agoand Rust will prevent data races, which F# won't.
- brighteyes 7y agoRust would have tradeoffs here, though. For example, in C# you'd be able to do (non-leaking) graphs and other structures in 100% safe code, while Rust would need unsafe.
- PudgePacket 7y agoYou don't need unsafe. This point is brought up a lot, though I understand where the misunderstanding can come from. Rust is perfectly capable of expressing graphs with zero unsafe code, just currently not in the most optimum implementation.
- ClumsyPilot 7y agoIs is fine, or suboptimal to the point of being impractical? Genuine question, how bad is this, if quanified?
- sanxiyn 7y agoIt is fine and practical.
- staticassertion 7y agoAdjacency matrices are trivial to implement in Rust. I leverage graphs constantly.
- pron 7y agoThere are sound static analyzers, like Trust-in-Soft, that can statically guarantee the absence of undefined behaviors in C programs, but require interactive work to get rid of the false positives. But the distinction between "runtime" and "compile-time" is not entirely binary. What you call "compile time" checks can be viewed as an abstract interpretation [1] of the program, or as running the program in some abstract domain -- e.g., where a concrete value could be 3, its abstract value could be called `int`, and the + operation could be interpreted as `int + int = int`; type inference could be viewed as abstract interpretation. The problem is that sound abstract interpretation (i.e., one without false negatives -- if it tells you your programs is "safe" then it will definitely be safe, for some appropriate definition of safe) is limited, and often comes with big tradeoffs, e.g. either false positives given by sound static analyzers or the pain something like Rust's borrow checker sometimes causes -- these are both instances of the same underlying difficulty with abstract interpretation. One of the most promising directions in formal methods research is "concolic testing" [2], which means a combination of concrete (i.e. non-abstract, or "runtime") execution and symbolic execution (an instance of abstract interpretation). It is not sound, but can be made quite safe, and at the same time it can be very powerful and flexible, checking properties that can be either impossible or extremely tedious, to the point of infeasibility, with abstract methods like types. It might prove to be a good sweet spot between the power, expressivity and cost of concrete (AKA dynamic, AKA runtime) methods and the soundness of abstract (AKA static, AKA compile-time) methods. Even dynamic methods are often "stronger" (more sound) than just testing assertions during testing. For example, fuzzers can sample the program's state space, offering more coverage, either by analyzing the program (whitebox) or just randomly (blackbox), and various sanitizers sample the scheduling space by fuzzing thread scheduleing. [1]: https://en.wikipedia.org/wiki/Abstract_interpretation https://en.wikipedia.org/wiki/Abstract_interpretation [2]: https://en.wikipedia.org/wiki/Concolic_testing https://en.wikipedia.org/wiki/Concolic_testing
- Gibbon1 7y agoI have an alternate opinion which is compile times should be fast because it done often. Where sanitization is something you only need to do in later release QA stages. SO it can be slow and that's okay.
- StavrosK 7y agoYou can have different "thoroughness" levels while compiling, though.
- nly 7y agoThere are ways to achieve some of this statically with annotations: https://clang.llvm.org/docs/ThreadSafetyAnalysis.html https://clang.llvm.org/docs/ThreadSafetyAnalysis.html