i feel that the grammar of a programming language is among the least appropriate of all possible facets of its behavior to start off with.
-
turns out a "hoare triple" is the fuckboy term for "precondition and postcondition" when you think you're the first to ever create an abstract machine for the C programming language
he never cites anything about a Hoare triple either
Hoare triples, where a block of code is preceded by a pre-condition and followed by a post-condition, have already appeared in §1.1.1.
he did just refer you, with a hyperlinked section heading, to the line above where he just says "triple"
The aliasing problem is much worse for inductively-defined data structures, where it is possible that structural invariants can be violated, and where we need more sophisticated recursive predicates to stipulate aliasing conditions.
this problem is so bad he has no example
These predicates appear in specifications, invariants and proofs, and their discovery is often a time consuming trial-and-error process.
sorry that you hate your job?
The aliasing situation becomes untenable when code is type-unsafe and we are forced to seek improved methods.
if the C compiler can unambiguously interpret it then maybe the C compiler is a better proof framework than isabelle/HOL
If instead we had a variable
float * p:{| True |} ∗p = 3 .14 ; ∗q = 42 ; {| ∗p = ? |}then not only do we have to consider aliasing between pointers of different types, but also the potential for p to be pointing inside the encoding of
∗qand vice versa.i don't know what language you're verifying but C has semantics here
We talk about this phenomenon as inter-type aliasing.
who's we
-
The aliasing problem is much worse for inductively-defined data structures, where it is possible that structural invariants can be violated, and where we need more sophisticated recursive predicates to stipulate aliasing conditions.
this problem is so bad he has no example
These predicates appear in specifications, invariants and proofs, and their discovery is often a time consuming trial-and-error process.
sorry that you hate your job?
The aliasing situation becomes untenable when code is type-unsafe and we are forced to seek improved methods.
if the C compiler can unambiguously interpret it then maybe the C compiler is a better proof framework than isabelle/HOL
If instead we had a variable
float * p:{| True |} ∗p = 3 .14 ; ∗q = 42 ; {| ∗p = ? |}then not only do we have to consider aliasing between pointers of different types, but also the potential for p to be pointing inside the encoding of
∗qand vice versa.i don't know what language you're verifying but C has semantics here
We talk about this phenomenon as inter-type aliasing.
who's we
While specifications may mention some state that is affected by the intended behaviour of a program, it is hard to capture the state that is not changed.
literally a nonsense sentence
In the above example, a client verification that also dereferences a pointer
r, not mentioned in the specification, has no information on its value after execution of the code fragment.meaningless
This limits reusability and hence scalability of verifications.
the C compiler is a better proof framework than isabelle/HOL
-
While specifications may mention some state that is affected by the intended behaviour of a program, it is hard to capture the state that is not changed.
literally a nonsense sentence
In the above example, a client verification that also dereferences a pointer
r, not mentioned in the specification, has no information on its value after execution of the code fragment.meaningless
This limits reusability and hence scalability of verifications.
the C compiler is a better proof framework than isabelle/HOL
now he's explaining why he trusts machine output more than anyone
Formal reasoning with the usual process of pen-and-paper mathematical proof neither scales as we would like in software verification nor has the expected degree of rigour.
you know humans made isabelle/HOL too right
-
now he's explaining why he trusts machine output more than anyone
Formal reasoning with the usual process of pen-and-paper mathematical proof neither scales as we would like in software verification nor has the expected degree of rigour.
you know humans made isabelle/HOL too right
"scales" i think he literally just means deskilling here. he's literally saying actually formal verification is more reliable than engineers you pay money to
-
"scales" i think he literally just means deskilling here. he's literally saying actually formal verification is more reliable than engineers you pay money to
now he's trying to mansplain "algorithmic verification" as if model checking in TLA+ https://lamport.azurewebsites.net/tla/high-level-view.html isn't actually extremely widely used in this exact space already
Research in this area has produced impressive results in recent years with improvements in the underlying theory and increased available computing power.
theory and computing power are the only things that produce impressive results. no i can't give you a citation it's not like this is my dissertation
They can catch increasingly wider classes of programmer errors
this is still a fucking hateful way to talk about formal verification
and even guarantee the absence of certain types of bugs.
such a half-assed phd thesis. do you even believe in what you're saying
-
now he's trying to mansplain "algorithmic verification" as if model checking in TLA+ https://lamport.azurewebsites.net/tla/high-level-view.html isn't actually extremely widely used in this exact space already
Research in this area has produced impressive results in recent years with improvements in the underlying theory and increased available computing power.
theory and computing power are the only things that produce impressive results. no i can't give you a citation it's not like this is my dissertation
They can catch increasingly wider classes of programmer errors
this is still a fucking hateful way to talk about formal verification
and even guarantee the absence of certain types of bugs.
such a half-assed phd thesis. do you even believe in what you're saying
@hipsterelectron TLA mentioned let's go -
@hipsterelectron TLA mentioned let's go
-
now he's trying to mansplain "algorithmic verification" as if model checking in TLA+ https://lamport.azurewebsites.net/tla/high-level-view.html isn't actually extremely widely used in this exact space already
Research in this area has produced impressive results in recent years with improvements in the underlying theory and increased available computing power.
theory and computing power are the only things that produce impressive results. no i can't give you a citation it's not like this is my dissertation
They can catch increasingly wider classes of programmer errors
this is still a fucking hateful way to talk about formal verification
and even guarantee the absence of certain types of bugs.
such a half-assed phd thesis. do you even believe in what you're saying
Proof creation has a high cost associated with it.
yeah you keep saying it sucks. aren't you supposed to fix things like that
To give an idea, it has been the author’s experience [93, 94, 96] that, in an interactive theorem prover, verifying the functional correctness of C code can require between one and two orders of magnitude more proof steps than line count,
(a) yeah maybe cause you keep trying to verify functional correctness guarantees about heap allocations in ring 0
(b) "line count" appeals to the VC class. it doesn't work on programmers -
Proof creation has a high cost associated with it.
yeah you keep saying it sucks. aren't you supposed to fix things like that
To give an idea, it has been the author’s experience [93, 94, 96] that, in an interactive theorem prover, verifying the functional correctness of C code can require between one and two orders of magnitude more proof steps than line count,
(a) yeah maybe cause you keep trying to verify functional correctness guarantees about heap allocations in ring 0
(b) "line count" appeals to the VC class. it doesn't work on programmersliterally everyone go read aaron turon's paper on weak atomic memory orderings right now https://plv.mpi-sws.org/gps/paper.pdf yes there's a coq proof but that's not what a paper is for!!!
check out this future work section:
However, the C11 model allows programmers to freely mix memory orderings, and ideally program logics should support such mixed reasoning as well.
literally it's that easy to give a shit about making people safe and providing powerful robust guarantees. this is why rust used to be good
Early investigation suggests that the C11 model has some corner cases when mixing memory orderings that may obstruct compositional reasoning principles.
i get nerd sniped every time i read that line lmao
-
literally everyone go read aaron turon's paper on weak atomic memory orderings right now https://plv.mpi-sws.org/gps/paper.pdf yes there's a coq proof but that's not what a paper is for!!!
check out this future work section:
However, the C11 model allows programmers to freely mix memory orderings, and ideally program logics should support such mixed reasoning as well.
literally it's that easy to give a shit about making people safe and providing powerful robust guarantees. this is why rust used to be good
Early investigation suggests that the C11 model has some corner cases when mixing memory orderings that may obstruct compositional reasoning principles.
i get nerd sniped every time i read that line lmao
We believe the extra generality of GPS is important because it enables us to verify a wider class of weak memory programs, including those whose observable behavior is not SC. The circular buffer and Michael-Scott queue are good examples of this (see the appendix [1]). Singh et al. [35] argue that one should not expose the high-level programmer to such non-SC data structures, but GPS shows that in fact it is possible to reason sensibly and modularly about them.
keep in mind seL4 doesn't even represent concurrent behavior at all in their 2009 proof (as far as i can tell), even though concurrency semantics are a feature on any system with a motherboard. and aaron turon shows actually we can make it easier to write complex code with formal verification
-
We believe the extra generality of GPS is important because it enables us to verify a wider class of weak memory programs, including those whose observable behavior is not SC. The circular buffer and Michael-Scott queue are good examples of this (see the appendix [1]). Singh et al. [35] argue that one should not expose the high-level programmer to such non-SC data structures, but GPS shows that in fact it is possible to reason sensibly and modularly about them.
keep in mind seL4 doesn't even represent concurrent behavior at all in their 2009 proof (as far as i can tell), even though concurrency semantics are a feature on any system with a motherboard. and aaron turon shows actually we can make it easier to write complex code with formal verification
honestly i should totally mess around with coq semantics for my ring buffer from hell
-
honestly i should totally mess around with coq semantics for my ring buffer from hell
oh yeah the other guy was telling me how much it sucks to verify stuff
and in a single person year, we may be limited to verifying no more than something in the order of 1000 lines-of-code (LoC). Little data exists for how proof-based projects scale, but it is unlikely to be linear.
still just ridiculous that this guy is still talking "verification" without doing the work in the c compiler. i know people do that
The economics of verification have two significant consequences.
so bleak to talk about your research focus like this
First, the range of systems we can hope to verify is limited, but is still large enough to be practically interesting.
that's literally not a "consequence" why would you invoke proof jargon incorrectly lmao
Modern microkernels, with implementations around 10,000 LoC are hopefully within the realm of possibility.
you were just a moment ago saying
int * p; int * q;was beyond your abilities -
honestly i should totally mess around with coq semantics for my ring buffer from hell
@hipsterelectron "ring buffer from hell" sounds incredibly exciting
-
oh yeah the other guy was telling me how much it sucks to verify stuff
and in a single person year, we may be limited to verifying no more than something in the order of 1000 lines-of-code (LoC). Little data exists for how proof-based projects scale, but it is unlikely to be linear.
still just ridiculous that this guy is still talking "verification" without doing the work in the c compiler. i know people do that
The economics of verification have two significant consequences.
so bleak to talk about your research focus like this
First, the range of systems we can hope to verify is limited, but is still large enough to be practically interesting.
that's literally not a "consequence" why would you invoke proof jargon incorrectly lmao
Modern microkernels, with implementations around 10,000 LoC are hopefully within the realm of possibility.
you were just a moment ago saying
int * p; int * q;was beyond your abilitiesVerification of such systems can bring significant improvements to the reliability of the entire software stack, as above the microkernel layer hardware protection domains limit the impact any incorrectly behaving software has on the trusted computing base [83].
- microkernels don't consider it their problem to provide any sort of correctness guarantees except for their own behavior, so this is just a lie.
- the MMU isolation is from the CPU, not the microkernel
-
Verification of such systems can bring significant improvements to the reliability of the entire software stack, as above the microkernel layer hardware protection domains limit the impact any incorrectly behaving software has on the trusted computing base [83].
- microkernels don't consider it their problem to provide any sort of correctness guarantees except for their own behavior, so this is just a lie.
- the MMU isolation is from the CPU, not the microkernel
i will literally die mad about how casually they mentioned fucking shared memory pages are a replacement for sequenced writes https://trustworthy.systems/publications/nicta_full_text/8988.pdf
In original L4, “long” messages could specify multiple buffers in a single IPC invocation to amortise the hardware mode- and context-switch costs.
a single crumb of structured I/O
While long IPC provides functionality that cannot be emulated
literally the actual criterion for minimality
Shared buffers can avoid any explicit copying be-
tween address spaces"microkernel layer hardware protection domains" cmon
-
i will literally die mad about how casually they mentioned fucking shared memory pages are a replacement for sequenced writes https://trustworthy.systems/publications/nicta_full_text/8988.pdf
In original L4, “long” messages could specify multiple buffers in a single IPC invocation to amortise the hardware mode- and context-switch costs.
a single crumb of structured I/O
While long IPC provides functionality that cannot be emulated
literally the actual criterion for minimality
Shared buffers can avoid any explicit copying be-
tween address spaces"microkernel layer hardware protection domains" cmon
The result was significant kernel complexity, with many tricky corner cases that risked bugs in the implementation.
i thought that's why we used formal verification? that's why microkernels were worth the cost of proofs?
-
The result was significant kernel complexity, with many tricky corner cases that risked bugs in the implementation.
i thought that's why we used formal verification? that's why microkernels were worth the cost of proofs?
after reading all this my impression continues to be that microkernels don't do enough isolation at all!!! i even dug up build systems a la carte https://www.microsoft.com/en-us/research/wp-content/uploads/2018/03/build-systems-final.pdf where simon peyton-jones tried to pull this same shit about build systems
-
after reading all this my impression continues to be that microkernels don't do enough isolation at all!!! i even dug up build systems a la carte https://www.microsoft.com/en-us/research/wp-content/uploads/2018/03/build-systems-final.pdf where simon peyton-jones tried to pull this same shit about build systems
i do actually appreciate that seL4 has a lot of use in single-core embedded applications where you're typically not just greedy for i/o like me and the purpose of an OS actually aligns reasonably well with the atomic i/o APIs
-
after reading all this my impression continues to be that microkernels don't do enough isolation at all!!! i even dug up build systems a la carte https://www.microsoft.com/en-us/research/wp-content/uploads/2018/03/build-systems-final.pdf where simon peyton-jones tried to pull this same shit about build systems
@hipsterelectron one of my gfs and I have a concept that has never been done before which we are working on in fits and starts which I think does what you want, or at least partway. the idea of extreme isolation, no longer having the idea of system calls at all but "cross-calling" and there being a dogmatic principle that ensures authority always and only ever flows from the user. everything can be halted, resumed, disassembled on the fly, etc, but only with direct user authority. I felt like we'd found a grail. It only works in a very small amount of x86-64 code rn kept private to avoid exposure before it is ripe but there's fully a way. not hurd, not a mircokernel, not a monolith, but a sherpa guide
-
i do actually appreciate that seL4 has a lot of use in single-core embedded applications where you're typically not just greedy for i/o like me and the purpose of an OS actually aligns reasonably well with the atomic i/o APIs
For seL4 there are even stronger reasons for staying away from supporting long messages: The formal verification approach explicitly avoided any concurrency in the kernel [Klein et al. 2009], and nested exceptions introduce a degree of concurrency.
i also very specifically want to avoid introducing subtle concurrency bugs but i'm doing that by expanding "isolation" beyond the MMU and expanding named "synchronization contexts" to structure literally all the externally-visible state changes like i/o
i absolutely don't think i could do seL4 better, and i'm not planning to inject tons of confusing and poorly-documented semantics like linux
