This isn't, however, DARPA's first foray into automatic program translation, or even automatic translation into Rust[2].
[1]: https://www.urbandictionary.com/define.php?term=DARPA%20hard
[2]: https://c2rust.com/
DARPA is a step closer to traditional research labs but there is obviously some overlap.
It's more like the NSF but focused on commercial grantees with project management thrown on top to orchestrate everything.
The really unique part is how much independence each program manager has and the term limits that prevent empire building.
(But yes: DARPA's mandate is explicitly to discover and develop the next generation of emerging technologies for military use.)
If you count my number of attempts, sure.
If you count by impact, it's hard to come up with many things more impactful than the Internet...?
(But even if DARPA was involved in Ada: I think it's clear, at this point, that Ada has been a resounding success in a small number of domains without successfully breaking into general-purpose adoption. I don't have a particular value judgment associated with that, but from a strategic perspective it makes a lot of sense for DARPA to focus program analysis research on popular general-purpose languages -- there's just more labor and talent available.)
I looked it up. DARPA was not involved.
You hate jumbo jets, high-speed trains, air traffic control, and satellites?
npm ERR! install Couldn't read dependencies
npm ERR! package.json ENOENT, open '/boeing/787-9/flaps-up.json'
npm ERR! package.json This is most likely not a problem with npm itself.
npm ERR! package.json npm can't find a package.json file in your current directory.once the maturity of the users advances to a sufficient point, then ada is the only solution.
"ada. used in creating reliable software since 1983"
when i first saw ada, i didn't understand the why. now i understand the why, but ada is effectively gone.
-- old fortran / C / Assembly programmer
Something unheard of, paying for software tools in 2024, who would imagine that.
gnat needs money. well deserved. but adoption needs a free, easy to install compiler.
5 years ago i had the pleasure of resurrecting a dead system. it was about 30k of ada, lets call it ada 87 (!). unknown compiler, 32 bit, 68K processor, 16 MB memory, unknown OS.
code was compiling in 2 days, running in 2 weeks. i needed to change from using 32 bit floats to 64 bit floats (seems positional data is a little more accurate in 2020). 1 declaration in 1 package spec and a recompile, and all my positions are good.
i love that language!
so, changed wordsize, processor, operating system... minimal source code impact.
How good the resulting performance would be like, that is another matter.
I'd say it's good timing.
You can attach about a hundred asterisks to that.
If anything, I think self the failure to hit L5 driving after billions of dollars and millions of man hours invested is probably reflective of how automatic C to Rust translation will go. We'll cruise 90% of the way, but the last 10% will prove insurmountable with current technology.
Think about the number of C programs in the wild that rely on compiler-specific or libc-specific or platform-specific behavior, or even undefined behavior plus the dumb luck of a certain brittle combination of {compiler version} ∩ {libc version} ∩ {linker version} ∩ {build flags} emitting workable machine code. There's a huge chunk of C software where there's not enough context within the source itself (or even source plus build scripts) to understand the behavior. It's not even clear that this is a solvable problem in the abstract.
None of that is to say that DARPA shouldn't fund this. Research isn't always about finding an industrial strength end product; the knowledge and expertise gained along the way is important too.
In 10 (or 2 or 50 or X) years when Chevy, Ford, and others are rolling out cheap self driving this argument stops working. The important thing is that this argument stops working with no change in how hard C to Rust conversion is.
We really should be looking at the specifics of both problems. What makes computer language translation hard? Why is driving hard? One needs to be correct while inferring intent and possibly reformulating code to meet new restrictions. The other needs to be able to make snap judgments and in realtime avoid hitting things even if it just means stopping to prefer safety over motion. One problem can be solved piecewise without significant regard to time and the other solved in realtime as it happens without producing unsafe output.
These problems really aren't analogous.
I think you picked self driving cars just because it is a big and only partially solved problem. One could just as easily pick a big solved problem or a big unstarted problem and formulate equally bad arguments.
I am not saying this problem is easy, just that it seems solvable with sufficient effort.
I'd put money on the solutions to said problems looking largely the same though - big ass machine learning models.
My prediction is that a tool like copilot (but specialized to this domain) will do the bulk of source code conversions, with a really smart human coming behind to validate.
The director orders the use of the tool when the dev team got downsized (and the two most-seniors left for greener pastures just after that). Validation is in the "extensive" tests anyway, we have those, right, so the new intern shall have a look, make it all work (fudge the tests where possible and remove the persistently failing ones as they've probably been always broken). The salesman said it comes from the DOA or DOD or something. If the spooks can do it so can we.
Which are things that took 20 or 50 years longer than expected in some cases.
> I think you picked self driving cars just because it is a big and only partially solved problem. One could just as easily pick a big solved problem or a big unstarted problem and formulate equally bad arguments.
But C to Rust translation is a big and only partially solved problem.
Even if it's "can handle well 90%" of the transition for any project, this is still interesting. Unlike cars on the road, most code transition project out there doesn't need to be 100% fine to provide some useful value.
Just getting something vaguely Rust shaped which can compile is the first step in overcoming the inertia to leave the program in its current language.
There is real utility in slowly fleshing out the number of transforms in a tool like c2rust that can recognise high-level constructs in C code and produce idiomatic safe equivalents in rust
It'll be great for "pure" functions. For the grimey parts of the world, funcs taking pointer args and returning pointers, for things that access and modify global data without locks, for threaded code with implicit (and undocumented) locking, the tool would add most value. If it can. Even only by saying "this code looks grimey. here's why. A bit of FFI will also be thrown in because it links against 100 libraries. I suggest changes along those lines ... use one of the 2000000 hint flags to pick-your-evil".
> You can attach about a hundred asterisks to that.
Not in San Francisco. There are about 300 Waymo cars safely driving in one of the most difficult urban environments around (think steep hills, fog, construction, crazy traffic, crazy drivers, crazier pedestrians). Five years ago this was "someday" science-fiction. Frankly I trust them much more then human drivers and envision a future utopia where human drivers are banned from urban centers.
To get back on topic, I don't think automatic programming language translation is nearly as hard, especially since we have a deterministic model of the machines it runs on. I can see a possible approach where AI systems take the assembler code of a C++ program, then translate that into Rust, or anything else. Can they get 100% accuracy and bit-for-bit compatibility on output? I would not bet against it.
Getting identical outputs on safe executions, catching any unsafe behavior (at translation-time or run-time), and producing efficient, maintainable code all at once is a million times harder.
But, this isn't just about rewriting code from one language to another. It's about reverse engineering complex information out of the code, which may not be immediately visible in it, and then finding a way to make it "safe" according to Rust's type system. Where's the training data for that? It'd be really hard even for skilled humans.
Personally I think the most pragmatic way to make C/C++ memory safe quicker is one of two approaches:
1. Incrementally. Make std::vector[] properly bounds checked (still not done even in chrome!), convert allocations to allocations that know their own size and do bounds checking e.g. https://issues.chromium.org/issues/40285824
2. Or, go the whole hog and use runtime techniques like garbage collection and runtime bounds checks.
A good example of approach (2) is Managed Sulong, which extends the JVM to execute LLVM bitcode directly whilst exposing to the C/C++/FORTRAN a virtualized Linux syscall interface. The whole piece of code can be sandboxed with permissions, and memory safety errors are caught at runtime. The compiler tries to optimize out as many bounds checks as possible. The interesting thing about this approach is it doesn't require big changes to the source code (as long as it's already been ported to Linux), which means the work of making something safe can be done by teams independent of the original authors. In practice "rewrite it in Rust" will usually mean a fork, which introduces lots of complicated technical, cultural and economic issues.
Managed Sulong is also a research project and has a bunch of problems to solve, for instance it needs to lose the JITC dependency and go fully AOT compiled (doable, there's no theoretical issue with it and much of the needed infra already exists). And performance/memory usage can always be improved of course, it regresses vs the original C. But those are "just" systems engineering problems, not rewrite-the-world and solve-static-analysis problems.
Disclosure: I do work part time at Oracle Labs which developed Managed Sulong, but I don't work on it.
Microsoft has this:
https://learn.microsoft.com/en-us/cpp/standard-library/safe-...
but it doesn't seem to actually make std::vector[] safe.
It's frustrating that low hanging fruit like this doesn't get harvested.
[1] "although there are precondition checks for some string operations, e.g. operator[], they will not always be run when using the char and wchar_t specializations (std::string and std::wstring)."
https://github.com/microsoft/STL/issues/586
> We talked about this at the weekly maintainer meeting and decided that we're not comfortable enough with the (lack of) design of this feature to begin documenting it for wide usage.
I tried a toy example with GCC [1], Clang [2], and MSVC [3], and none of them emit bounds checks with basic optimization flags.
[1] https://godbolt.org/z/W5e3n5oWM
That might not be too bad.
A combination of a formal system and an LLM might work here. Suppose we see a C function
void somefn(char* buf, int n);
If it's an array, how big is it? We don't have enough info to know that yet. But a reasonable guess, and one than an LLM might make, is that the length of buf is "n".
Following that assumption, it's reasonable to translate this to Rust as
fn somefn(buf: &[u8])
buf.len()
assert!(buf.len() == n);
somefn(buf, n);
fn somefn(buf: &[u8], int n)
The idea is to recognize common C idioms and do clean translations to Rust for them. This should handle a high percentage of cases.
But if you're going to do it that way, the right place to start is probably to a safer form of C++ not Rust. That way code can be ported file-at-a-time or even function-at-a-time, and so you'll have a chance to run the assertions in the context of the original code. Which of course may not have good test coverage, as C codebases often don't, so you'll have to be testing your assertions in production.
There's something to be said for that. You're going to need at least an internal representation that's a safe C/C++.
Most compilers do have flags to turn this on, which I use all the time.
The issue is the "performance trumps safety" culture that pushes back against using them.
This is an excellent example of government action I like to see, as it isn't about favoritism or the swamp dynamics. Just provide a target, a bounty and no or low barriers to entry.
This challenge does push Rust out in front of everybody. That's a mixed blessing. I hope this challenge gets modified to not specify the target language, but instead the requirement of memory and type safety. Rust is likely an intermediate stop on the way to something better, and it shouldn't matter if that language is called Rust 2.0 or something else.
and it's open source as well! http://rosecompiler.org/ROSE_HTML_Reference/index.html
I can't believe that works at all. I'll take a look for sure.
It would be most interesting if the approach was not to feed the program the original program but rather the manual for the program. That said it's rare that a manual captures all of the nuances of the program so a view into the source code is probably necessary, at least for getting the ground truth.
"AI more or less sort of summarizes the features of the program into some approximate kind of technical language, then the AI synthesizes something not too far from Rust code that hopefully covers aspirationally the same feature set".
Usually the biggest issue, is that most of the porting attempts don't start there, rather they go for the rewritte from scratch, and lets not pay the licenses for those cross-compilers.
Additional training data can be generated by running mrustc or by inlining unsafe code (from std/core/leaf crates) into safe code and running semantics-preserving mechanical refactorings on the code.
This can be closer to AlphaProof than ChatGPT
If you think it's hard wrestling with the borrow checker, just imagine how much harder it is to write automatic translation to borrow-checker-approved code that accounts for all the possible program space of C and all it's celebrated undefined behavior. A classic problem of writing compilers is that the space of valid programs is much larger than the space of programs which will compile.
A quick web search reveals some other efforts, such as c2rust [1]. I wonder how TRACTOR differs.
That’s not what they are aiming for. FTA: “The goal is to achieve the same quality and style that a skilled Rust developer would produce”
> just imagine how much harder it is to write automatic translation to borrow-checker-approved code that accounts for all the possible program space of C and all it's celebrated undefined behavior
Nitpick: undefined behavior gives the compiler leeway in deciding what a program does, so the more undefined behavior a C program invokes, the easier it is to translate its code to rust.
(Doing that translation in such a way that the behavior remains what gcc, clang or “most C compilers” do may be harder, but I’m not sure of that)
That's the kind of language lawyer approach that caused a rebellion in the last decade amongst C programmers against irresponsible compiler optimizations. "Who cares if your program actually works as intended? My optimization is legal according to the standard, it's your program that's written to exploit loopholes".
I don't see any evidence that that's the attitude being taken by TRACTOR — I sure hope it isn't. But hell, even if the result is unreliable in practice, I suppose that if somebody gets to claim "it works" then the incentives are aligned to produce garbage.
If your program invokes undefined behaviour, it's invalid and non-portable. Out of bounds array accesses are UB, yet a program containing them may just happen to work. It won't be portable even between different compiler versions.
The C standard is a 2 way contract: the programmer doesn't produce code that invokes undefined behaviour, and the compiler returns a standard conforming executable
I don't feel that the Rust language situation incentivizes such awful conflict, and it's one of many reasons I now try really hard to avoid C and use Rust instead.
But I don't think defining all behavior helps. The defined behavior could be /wrong/, and now you can't find it because the program using it is valid, so it can't be detected with UBSan.
Undefined behavior is usually a result of runtime situation, it is usually not obvious from just the code whether it could or could not happen, so the compiler cannot reject the program.
The 'UB-based' optimization is just assumption that the code is correct and therefore UB-situation could not happen in runtime.
> The standards added the forward progress guarantees to change an optimization problem from "solve the halting problem" to "there will be observable side effects in the forms of termination, I/O, volatile, and/or atomic synchronization, any other operation can be reordered". The former is generally impossible to solve, whereas the latter is eminently tractable.
But yeah, that's one of the more foot-gunny UB rules that Rust does not have. But it does mean it doesn't mark functions as `mustprogress` in LLVM IR which means it misses out on whatever optimizations that enables.
You significantly underestimate how much UB people write and overestimate the end-result if the current approach would not be taken.
I don’t see any way it can do otherwise. As a simple example, what would one translate this C statement to:
int i;
…
i = abs(i);
let i: i64;
…
i = abs(i);
unsafe {
let mut i: std::os::raw::c_int
= std::mem::MaybeUninit::uninit().assume_init();
// ...
i = libc::abs(i);
}
Given that generated code, I could then piecemeal migrate the unsafe bits to cleaner, idiomatic safe rust: possibly your code but more likely `i::wrapping_abs()` or similar.
What will TRACTOR choose? At least for this example, they don't have to choose inappropriate pruning of undefined behavior. They claim the following:
> The goal is to achieve the same quality and style that a skilled Rust developer would produce, thereby eliminating the entire class of memory safety security vulnerabilities present in C programs.
If they're going to uphold the same "quality", the translation you presented doesn't cut it. But you may be right and they will go down the path of claiming that a garbage translation is technically valid under undefined behavior and therefore”quality” — if so, I will shun them.
[1] https://play.rust-lang.org/?version=stable&mode=debug&editio...
Because of the leeway the C standard gives you, you can preserve the semantics of the C program by just calling abs, and I think that’s the best you can do.
What the compiler does may be different for different compilers, different compiler versions or different compilation flags, so if all you have is the C source code, there’s no way to preserve the semantics of the machine code that the C compiler generates.
You could special-case all of them, but even then, there is the problem that a C compiler, even in a single translation unit, can inline one call and then apply some transformations while compiling another call to a call to a library function, making the semantics of overflow in one location different from that in another.
If you want to replicate that, I’d say you aren’t writing a C to rust translator, but a (C + assembly) to rust translator.
Also, if you go this route, you’d have to do similar gnarly stuff for all arithmetic on integers where you cannot prove there will not be overflow. I would not call the resulting code idiomatic rust.
To uphold the spirit of Rust, a C program must go through a process where assumptions are laid bare and footguns are dismantled. Applying an automatic process which arbitrarily changes the behavior from the implementation-dependent compilation of a C program just gets you a messy slop of hidden bugs collected inside an opaque, "safe" garbage can.
You don't get to Rust's reliability by applying a translation which discards it!
> Also, if you go this route, you’d have to do similar gnarly stuff for all arithmetic on integers where you cannot prove there will not be overflow.
Damn straight. That's what C is! It was always this bad, as those of us who have struggled to control it can attest. Faithful translation to unsafe Rust just makes it obvious.
It may be better to just leave the assignment off the declaration. If the variable is read before it's initialized to something, we'll get a Rust compilation error, forcing programmer intervention. Detecting actual bugs that would result in memory errors and forcing them to be resolved is very much in the spirit of Rust. TRACTOR may aspire to gift C programs with memory safety for free, but it won't always be possible.
Of course if TRACTOR can determine through static analysis that the unitialized read can't cause problems, it might emit different code.
You assume that the compiler can determine what behavior is undefined. It can't. C compilers don't just look at some individual line of the program and say "oh, that's undefined, unleash the nasal demons". C compilers look at code, reason that if such-and-such variable has a certain value (say, a null or invalid pointer), then such-and-such operation is undefined (say, dereferencing that variable), and therefore on the next line that variable can be assumed not to have that bad value. Despite all the FUD, this is a very limited power. C compilers don't usually know the actual values in question, all they do is exclude some invalid ones.
Can't design a system that 100% crashes on invalid behavior if you've declared that behavior is valid, because then someone is relying on it.
And while DARPA doesn't directly care about research publications as an outcome, there's certainly a publishable research component to this, as well as a lot of lower papers-per-$ engineering and validation work. A lot of the contracts they hand out end up going to some kind of contractor prime (BBN, Raytheon, that kind of company) with one or more academic subs. The academic subs publish.
what you describe is exactly my experience as a darpa performer (on a program which dan is apparently now the pm for!)
You're just asking for people to bring out their pitchforks :P
> most interesting code is written in C++ anyway.
Really?! The Linux kernel is a _pretty enormous_ counterexample, as are many of the userland tools of most desktop Linux distros.
I am also a key developer of an entirely-written-in-C tool which I'd venture that [a large fraction of desktop Linux users in corporate environments use on a regular basis](https://gitlab.com/openconnect/openconnect).
Then you get into stuff that's not kernels and the user-spaces are again mostly all C++. The few exceptions that exist are coming out of the 90s UNIX culture, stuff like Apache or nginx. Beyond that it's all C++ or managed languages.
Whether or not the decision not to use C++ is good or bad, rational or irrational, what is the relevance?
The point is that the Linux kernel is technologically interesting and innovative, under very active development, and it's written in C.
> The few exceptions that exist are coming out of the 90s UNIX culture, stuff like Apache or nginx. Beyond that it's all C++ or managed languages.
I literally just told you about a software project to which I contribute, which thousands of people and organizations use, which is written in C.
Also, it wasn't written in the ’90s.
Isn't it equivalent to statically determining the lifetimes of all allocations in the C program, including those that are implemented using custom allocators or which cross into proprietary libraries? There's been a lot of research into this sort of thing over the years without much success. C/C++ programs can do things like tie allocation lifetimes to what buttons a user clicks, without ref counting or other mechanisms to ensure safety. It's not a good idea, but, they can do it.