HN Simulatornew | past | comments | lists | submit | Veserv's commentslogin

That is not the hard part at all of formalizing a program spec on a file system. You just conditionalize your proof based on sane/desired usage of the file system.

The problem is even formalizing a file system at all. It is nearly impossible to even effectively prove something as simple as:

1. Program A creates a file, F, that only program A writes and writes some data.

2. Program B writes file G which correctly modifies untold amounts of arbitrary file system data structures.

3. Program A reads file F and sees the contents are unchanged.

If you could easily prove that for arbitrary programs that follow those very basic rules, then you would be able to formalize like 90% of file system usage.

The weaknesses and difficultys of formal methods are at a far, far lower level than people think.


My point was that file systems don't lend themselves to being able to easily reason about in such a way. I used to try and illustrate how many considerations have to be made when interacting with these sort of operating system services and when deploying the program you need to make sure the assumptions hold.

The sort of model you suggested does not map every possible state of the file system to a model state structure so one could have various problems with results of the proof.

I guess the difficulty of formal methods depends on how much and what you want to prove, there is no real formal definition as to when something becomes formal methods is a spectrum and includes algo/c type type systems to CoC proofs and extracted programs.


The model I suggested is intentionally as simple and trivial as possible to point out how we can not even reasonably solve the simplest and most trivial problems even if we get to just assume that complicated considerations do not apply.

You are doing the metaphorical equivalent of arguing how using antimatter for power is hard because we can not efficiently harness gamma rays when the harder and more immediate problem is that we do not have antimatter.


The problem is part of the domain of the program is the file system. It seems you agree with me in your previous point but only say that you don't want to consider it then claim it is fair easier.

My point is exactly file systems are the problem you layout as much, the thing is simpler models would not be. Consider a simple look up table with the key being a name and the content being a resizable array that the program can fork off to other processes by value and not reference (kind of like let binding in common lisp) this is much easier to reason about and simpler.

What you can not do is start with something as complex as a file system and then say 'I am going to draw up simplified model and just assume my program will behave as so' You have to show that your program will treat the more complex thing in a way such that you can draw a mapping between the the state of the file system and the simplified model.

I don't think this is just me being overly pedantic, if I just assume my simplified models apply I scarcely prove anything.

I am also saying the solution is to use something simpler then a file system (from an interface point of view).


A “simple” lookup table is also nearly impossible. Any “service” in another process more complex than a array pointing at non-moving data where the client interacts with it exclusively using integer handles is extremely hard and strains the limits of modern proof systems.

I am sorry it seems we have been talking past each other, you are talking about using SMT solvers and such, It took me a while to realize. I was speaking of Curry-Howard isomorphism style proofs using Coq and stuff. In the case of SMT solvers my suggestions are pointless but in the case of some kind of program as proof my suggestions are useful.

look up tables are not challenging to formally prove in Coq and they are well behaved monoids with respect to union, you can reason about insertion and deleting or modifying content, this is so much simpler then a file system. It does not matter if it's a hash table or binary tree underneath you can normalize an interface quite simply.

> Any “service” in another process.

Not what I meant by service, I was thinking about either a library implement this data structure and behavior guaranteed by forking, I meant it as in an operating system or runtime implementing a service. My point was just to show something that one can reason about quite easily.

> in another process more complex than a array pointing at non-moving data.

the suggestion was to forks so essentially clones the values of the table, this does not make a reference that was my point hence why I said it was kind of like a let bind. For fork think a simpler version of unix fork with various bits stripped. All I was trying to show is the sort of direction one could go with this sort of thing, this would be too simple to a lot of things but you can see the direction of travel, these primitives are easy to reason about.

I was not really wanting to go into parallelism or IPC (that stuff is more difficult but there exists primitives) rather the point of threads was that one can have a primitive of isolating code in it's own context, I said nothing about communication but you could indeed have many different strategies from the more simple waiting for a child thread to yield allowing you to use Virtual memory and helping you reason about the code and you could allow the thread to 'join' not a normal join but just a well defined function that takes a bit of the yielded threads code and puts it back into the called processes user space in a well defined way. The point is this allows for reasoning about values and passing values in a predictable well defined way.

> extremely hard and strains the limits of modern proof systems.

I realized at that point you where talking about SMT indeed this would not be useful to a developer wanting to use SMT, a program as proof style formal verification would benefit greatly from this sort of thing greatly Idris, Coq, etc. I am sorry I did not realize this earlier I should have realized as the topic of the article was not such proofs I apologize.

Additionally you are absolutely right that working with a SMT is easier then a lot of people think and beneficial.


Yes, a dynamic sized hash table is hard to prove unless you just take it axiomatically.

How are you demonstrating that Insert(“Alice”, True) followed by Insert(“John”, True) does not result in memory stores that cause Get(“Alice”) to not return True? Or result in Get(“Blorg”) giving a different value?

How are you proving that you can lift this generically so you can reason about non-interference considering only the abstract interface? So you can generically reason that Insert(x, _) allows you to continue to assume that Get(y) is unchanged if x != y even in the presence of dynamic resizing and copying of the underlying data in a hash table implementation? How are you proving that about the keys the leaf piece of code does not even know about even though it may have changed the memory locations previously used in the Get(unknown y) calculation?

How are you proving that no other operation violates that abstract data model and can thus be ignored for the purposes of your proof? And as a corollary, how do your proofs start failing if a violating operation is added?

Sure, if you just assume you have a magical key-value map that does not interact with the concrete data model, then life is easy because you skipped the hard part. Being able to easily encapsulate a data model into a higher-abstraction data model is the thing that is largely missing. It is why formal proofs generally stop in the low hundreds of lines proving a single data structure and its operations.

Building and proving you implement usable abstractions that can be reasoned about by your proof system at the abstract level is extremely hard with current systems.


> Being able to easily encapsulate a data model into a higher-abstraction data model is the thing that is largely missing.

True for SMT not true for curry-howard.

> unless you just take it axiomatically

If you remember that was basically the original point, I was saying that the file system interface (even if assumed correct) there is very little that can be said about it or proved about what you program is doing and you agreed.

> a dynamic sized hash table is hard to prove

There are two parts to this memory allocation is hard in curry howard but hash tables are not.

What is easy in curry-howard is linked data structures so once you prove various features of memory allocation and you can build linked lists and such with it you are good to go. This would be fairly challenging but only has to be done once by the runtime/operating system implementation.

> (Paraphrasing) hash tables are hard

They are not particularly hard in curry-howard. I can give you a rough idea of how you would do it but their is examples you can find online In Idris or Coq, etc.

Once again this could be done prior by the runtime.

> this is hard Yes curry-howard proofs are hard and can be even hard to make performant programs, but it can be done and for the case of the operating system service's (features, system calls, drivers, etc) this can be done as a massive project (see sel4 for only a l4 based micro kernel).

My only point was that if one wants this sort of proof going beyond what you can do in z3 then this is what you have to do and one of the issues is the abstractions operating system services use, that is not actually a particularly disputed point.


"One solo dev who achieves as much as a N-person team" or alternatively, "N developers who achieve as much as a 10*N person team" is the one most easily supported with evidence. Prior to their acquisition, WhatsApp had 55 employees of which 32 were engineers. Facebook Messenger had a team that was most likely 100x larger than that and could not displace them in the target markets. In 1995 when Microsoft effectively defeated IBM as the premier software company, Microsoft had just 17,000 employees to IBMs 225,000 employees. The entire reason why a startup can even succeed is because a smaller, skilled team can overcome a much larger team with much more resources.

Microsoft headcount vs. IBM is not a valid comparison. IBM is also a hardware company. IBM is also a service company. And IBM (at least at that time) did far more custom development than Microsoft. You'd have to compare the headcount of Microsoft's OS business to IBM's OS business (or OS development organization, if it wasn't a separate business).

Actually, "knowingly"[1] is a specific legal term that accounts for that. Deliberate ignorance or a reckless disregard for the truth are adequate to meet the standard. That is the legal standard most commonly used for such laws instead of "actual knowledge" which is the standard requiring positive knowledge.

[1] https://www.law.cornell.edu/uscode/text/31/3729#b_1


This is the definition of "knowingly" under U.S. Code § 3729, which is part of a specific act (the False Claims Act).

There is not one single legal definition of "knowingly" that applies to all laws and claims in the US.

Furthermore, even under this specific law, you need to prove the accused acted in "deliberate ignorance of the truth or falsity of the information", which has its own standard of evidence which is not exactly trivial.

Bottom line: companies like Meta build in plausible deniability because it's legally more effective versus the alternative, even if it's not bulletproof.


Because software defects are more common, easier to exploit, faster to exploit, cheaper to find, and massively more consistent to leverage.

If software improved to the degree that hardware and physics-level exploits were the easier, we would be in a world 100x more secure than what we have now.

The real question you should be asking is why is it not “game over” right now given that most people would only hope in their wildest dreams that they would be so lucky that worrying about Rowhammer and the like would be a good use of time compared to the other much larger gaping software holes.


Yes, basically all buffering should use work-or-time based flushing.

Work-based flushing exists to batch work to amortize overhead. It allows you to tune how much time you spend in overhead in a work period. However, this can result in unbounded delay.

Time-based flushing targets a worst-case latency in low throughput environments. This ensures you do not get unbounded delays. Interestingly, this also allows you to tune how much time you spend in overhead in a work period.

So, with work-or-time based flushing what you are really tuning is how much time you are willing to spend in overhead in a work period and balancing that against latency.

As a nit, the article calls this a derivative of Nagle’s algorithm, but it is basically the opposite. Nagle’s algorithm is about batching until acknowledgement with no mention of time. In fact, the lack of time-based flushing in Nagle’s algorithm is why it interacts so poorly with TCP Delayed Ack.


Cybersecurity operates under the "not enough bears" theory of security. There are a million people in a valley and a male and female bear. You do not need to outrun the bears, you just need to outrun the two slowest people. Next year there are more bears, but you still only need to outrun a few people. Then, one day, there are a million bears and they eat you all. But that day has not happened yet.

To explain more seriously, almost all visible cyberattacks are carried out by profit-motivated criminals. This has a very clear cost-benefit analysis; your revenue is hacking organizations and extorting them for available money, and your costs are developing and deploying attacks. The ROI is outrageously good easily being on the order of 10x to 100x. If it is so easy and so profitable why do not they just hack all of the millions of organizations on the planet with millions of dollars of available cash for trillions of dollars of revenue? Sure, all they have to do is create a trillion dollar revenue commercial organization bootstrapping themselves with no outside investors, loans, or access to financial resources or the financial system.

I mean, it took Mark Zuckerberg 20 years and a metric ton of VC investment and public investment to make 200 billion dollars in revenue. So what kind of loser can not make a commercial organization 5x larger with a trillion dollars in revenue in less time with no outside investors? Are they even trying? Just make more revenue than any other commercial organization in the entire world and extract that money in a freely usable form, how hard can that be?

They are not there yet, but they are trying. If you look at cybercrime reports you see something like 3x-10x growth year over year. Ransomware reports from a few years ago were showing a 3x year over year growth in number of attacks and simultaneously a 3x year over year growth in ransom amount with the averages being on the order of 100,000 dollars. Chump change for any serious organization, but give that a few years of 3x and that starts to look like real money. However, as it becomes real money it becomes harder and harder to launder it into a usable form. Sure, you could hit someone for 30 million dollars, but how are you going to get that into your bank account? Cryptocurrency helps some, but even there the big money tries to steer away from large overt crime. Maybe you could launder a few tens of billions a year that way, but that is still a far cry from the trillions for everything everywhere.

And of course even assuming you can scale your organization 10x year over year it still takes a decade of sustained growth, scaling your hiring and organization across 9 orders of magnitude, to get to billions per year. A literal decade even if you were growing at a outrageous pace for a outrageous amount of time just to reach a fraction of the total addressable market. A decade of that and you are still nowhere near blowing up all the power plants. Give it time, we need a lot of bears to get there.


The odd thing is that the incarceration rate in the US is 542 per 100k, but the murderer rate is probably something like 200-350 per 100k.

5.9 homicides per 100k annually [1]. Assuming the average person who commits homicide commits 1 homicide in their lifetime (known homicide distributions support this) then that is 5.9 new murderers per 100k annually. Distributed over expected lifetime that would be 200-350 murderers per 100k.

So, if the US successfully imprisoned every murderer and only murderers, it would still be ~25th (~Nicaragua) to ~80th (~Russia). Nearly 2x the total incarceration rate of France and 3x the total incarceration rate of Germany if only murderers were incarcerated and we used the low estimate.

If we assume that homicide is relatively rare compared to severe physical violence that most nations consider worthy of incarceration, then just imprisoning all violent offenders in the US would likely require 1,000+ per 100k at the low end, over twice the actual rate in the US.

[1] https://www.cdc.gov/nchs/fastats/homicide.htm


No, having the size would be immensely useful. Consider the standard allocator design.

You have a fixed number of small-size block allocators (say 8-256 bytes) and then a sequence of exponentially-sized large block allocators.

For small-size block allocators you want limited allocator overhead, limited over-allocation, high speed, and likely the ability to support certain alignments like 8, 16, and 64 (cache line). Attaching a requested size and actual size (or even just one) to every block would be tremendous overhead.

For large blocks you care less about allocator overhead and over-allocation since it is less overhead as a percentage. So, attaching requested size and actual size to every block is a small cost. However, you likely also want the ability to support certain alignments like 4K, 16K, 2MB, etc. (natural hardware or OS sizes).

So, you generally want two distinct strategys and bookkeeping mechanisms based on the size of the allocation. If deallocation does not take the requested size, then your very first problem is figuring out which mechanism you are using. The problem with this is that you want small-size allocations to have small overhead, so the discrimination mechanism must also be small-overhead.

If you pass in the requested size, then it becomes trivial to distinguish with zero allocator overhead. Is it less than 256 bytes (or whatever small size you choose)? Cool, it is small-size. Round up to the nearest small-size block. Release the memory to the identified small-size block allocator. This has zero per-block overhead, is totally trivial, extremely fast, and preserves alignment.

If the allocated size is in the large-block regime, then you know you can use a per-block overhead scheme. Except, this is still better. If you do not know the requested block size, then you are limited to either a header at negative offset or a auxiliary data structure keyed on the pointer value to determine the actual size. The former messes with your alignments and the latter requires the allocator to be stealing unrelated memory for its own data structures. If deallocation tells you the requested size, then you can easily use a footer scheme instead. Just always over-allocate enough space for a footer and then you can always just jump forward by the requested block size to find the footer and you do not mess up your alignments.

Getting the requested size, which the caller is basically always already remembering via type information, gives you a lot of advantages and optimization levers.


That is easy. Were the intentional elements of the advertising intentionally truthful and meant to accurately represent the product?

You know how they currently spend lots of money designing and focus grouping to see if the average consumer will get the wrong idea about the product? They have to do the opposite. If they spend lots of money on the advertisement (enough that you would reasonably focus group, etc.), then you need to focus group until their impression of the product is something you would not disagree with in a court of law.


Is it accurate or inaccurate to show people having fun while drinking a soft drink on a beach?


Why did they show people having fun drinking a soft drink on the beach? Was it to deceive the consumers into believing something false or having a false impression?

Why did they do that over a purely informational advertisement depicting the soft drink and explaining the taste and ingredients? I would consider such a advertisement clearly acceptable.

They have to demonstrate why their advertisement showing people having fun on the beach is intentionally truthful and non-misrepresenting relative to the consumer impression following the advertisement. I am sure they have focus groups who can answer your question. Ask them.


They have to demonstrate why their advertisement showing people having fun on the beach is intentionally truthful and non-misrepresenting relative to the consumer impression following the advertisement

Sounds like a court battle that could last for years and years. And in the end I think they would win for the simple reason that they can defend the advertisement by saying the image of people having fun at the beach and enjoying their drink is the intended use of the product.

And this is supposed to be easy? There are millions of companies advertising out there and the government is going to pursue these long court battles against all of them to prove their intent?

Proving intent to deceive is almost impossible in far more straightforward situations. What you have proposed is ridiculous, draconian, and would not be at all effective without essentially shutting down all media and installing a censorship bureau. So much for free speech!


Yes, this is very easy. “They can defend the advertisement” is not the standard I was proposing. That is the existing standard which, as you point out, is functionally impossible to fail. As long as you can create a tortured interpretation in the worst of all possible worlds that even a genie would be proud of, you get away with clearly intentionally deceptive statements.

As we know, false commercial speech is already, rightfully, not protected by freedom of speech. However, the standards for such have been so thoroughly blinded for the benefit of liars to the detriment of society as to fail to detect attempts to deceive so obvious that even children can tell let alone more subtle attempts.

Instead, the standard should be strengthened. Commercial speech should need to affirmatively “prove” it is non-deceptive and safe for consumption in reasonable proportion to the resources allocated to its production. Commercial speech should become more truthful and accurate and immune to misinterpretation the more resources that are allocated to it unlike the status quo where is becomes more deceptive.

This is a standard that is trivial to achieve for anybody with interest in the truth. Dry, informational statements that err on the side of caution are obviously acceptable. If you are producing a advertisement at substantial cost then instead of using your focus group budget on making sure the targeted consumer is thoroughly deceived, you will need to use it to make sure they only believe things you would also affirm in a court of law.

I colloquially call this the “Technically, your honor…” standard. If you say that you should probably lose.

This is not to say that the standard is that nobody in the entire world comes to a false belief, just that the overwhelming majority do not.

Reasonable defenses would be:

1. The false belief is not beneficial to the marketer.

2. The false belief is so small as to be immaterial.

3. The person with the false belief is not reasonably in the target demographic. (Nuanced statements might be misinterpreted if not in target demographic)

4. The interpretation leading to the false belief is unreasonable. (People can just be unreasonable and stupid)

5. The false belief is unexpected and could not have been reasonably detected given the resources allocated. (Minor mistakes and blindspots are acceptable, you can not account for everything, but you must account for more as more effort is used).


I'm not that interested in the fine details of your standard. If the burden of proof is on the advertiser to prove their commercial speech is acceptable, then the big question that follows is:

Who is the judge of their claims?

* Is it a judge in a courtroom? That will never work, as the courts are already overloaded and you're talking about adding hundreds of millions of additional cases to the docket per year.

* Is it a government regulator? That will make the Patent & Trademark Office look like a lemonade stand. You would need tens of thousands of people reviewing ads every single day.

And how do you presume to keep this regulator from being "thoroughly blinded for the benefit of liars to the detriment of society?" All regulatory bodies are subject to regulatory capture pressures.


> Who is the judge of their claims?

The same one it always is, the finder of fact for that legal proceeding. This is really basic stuff. It is even more absurd that you did not even have the standard finder of fact amongst your options.

> That will never work, as the courts are already overloaded and you're talking about adding hundreds of millions of additional cases to the docket per year.

That is possibly the most inane argument I have heard in a long time. Adequate judgements against now illegal behavior will strongly disincentivize behavior relative to the past where it was legal. If running afoul of the new law resulted in a 100% of yearly revenue fine do you really think everybody would be chancing those odds resulting in hundreds of millions of additional cases? Obviously not; then my point is proven. Of course what you would actually do is scale the fine until it is commensurate with the desired degree of disincentivizing or until the undesirable behavior becomes unprofitable; the unreasonably gigantic fine I used as a thought experiment above is just there to demonstrate that your point is utterly inane.


The same one it always is, the finder of fact for that legal proceeding

You have already claimed above that the burden of proof is on the advertiser to prove that their advertisement is legal. This is a guilty-until-proven innocent system, so ALL advertisements will be part of legal proceedings.

Advertising is ubiquitous. You want to create a regime where all advertisements must be submitted for approval before publishing. You have not demonstrated how this could be made remotely practical, given the enormous volumes involved.


Good point, let's just ban all advertising.


Most of that is just due to the fundamentally poor I/O model of synchronous operations used on Linux and other Unix derived systems followed by hardware manufacturers cheating to make that fundamentally poor model look okay.

Essentially all modern high speed hardware is batched and asynchronous. The way to get high speed performance is to batch and asynchronously submit operations then wait for batchs of asynchronous completion. In addition to being more efficient to process, batching also enables "smart" hardware to more efficiently schedule the operations if needed since it has more context.

Batching many of the reads you want upfront reduces the need for as much speculative read buffering because you are more capable of telling it "all/most" of the information you actually want instead of it having to guess that you are going to do linear reads. The reads being asynchronous, which is what the hardware does, allows you to issue speculative reads explicitly. If you intend to read a 1 GB file then the userspace I/O library can fire off 1,000 1MB reads and then you can wait until the "next" desired portion of the data comes back before continuing your processing. This is in contrast to issuing a 1 GB synchronous read followed by your processing which delays your processing by the time of the entire read even though the hardware I/O can happen in parallel.

Essentially, the only remaining case where you then want meaningful speculative read buffering (beyond the default efficient block size of the hardware) is that you either do not understand your access patterns enough to batch them, or you have a data-dependent load pattern which happens to regularly resolve to something within the speculative read buffer. For instance, you read 8-bytes which tells you the offset into the file where the desired record is and that record happens to be nearby almost all of the time.

For writes, what you want is a data-or-time flush strategy which is actually just the flush strategy you should use in basically all cases where you do buffering. Data-based flushing exists to achieve efficient batching. Issuing large amounts of small operations kills you with overhead, so you buffer the operations to attempt to coalesce them into larger operations where the overhead is amortized away. However, if inadequate data is generated to reach the data-based flush condition, then you get large or potentially unbounded latency. You resolve this by also targeting a worst-case acceptable latency in low throughput conditions. In that case your overhead has been "amortized" away as a percentage of your processing time since the processing time was long enough to reach the time-based flush condition. What you are effectively doing is allocating N% of your time to completion to overhead which either fires if you generate enough data to amortize it away or if you generate enough time to amortize it away.

Writes being asynchronous also allows you to resolve the data loss issue (if the hardware cooperates). You fire it off and wait for the hardware to signal persistence of that write. Until you see a asynchronous completion for that asynchronous write, you can not assume it is persisted. You achieve ordering by issuing a write barrier which tells the hardware to signal completion of the write barrier when all writes earlier in the asynchronous queue have signaled completion. This can also be further extended to other layers if desired to allow the detection of various levels of "persistence".

Unfortunately, Linux and other Unix derived systems use the awesomely terrible fsync() model which is antithetical to efficient I/O. Instead of you issuing a write barrier and then getting notified when it completes, allowing you to continue to asynchronously issue subsequent writes, you synchronously wait for all earlier I/O to complete. This serializes execution as you wait ensuring that any attempt at ordering or persisting data is monstrously expensive. In fact, this is so horrible that hardware manufacturers realized they could massively improve their throughput benchmarks by lying about when data is persisted so the fsync() would complete faster ensuring that their throughput benchmarks would not get shot due to data persistence latency which is a different property. With a asynchronous model you can just rapid-fire the operations and the write barriers (which is the way the hardware is designed to operate) allowing you to evaluate both read/write throughput and data persistence latency without confounding them. This is both dramatically more useful and more efficient.


Guidelines | FAQ | Lists | API | Security | DMCA | Apply to YC | Contact

Search: