Hacker News Reader

Comment by goalieca | Hacker News Reader

> As the KRACK paper points out, there is no formal description of the 802.11i handshake state machine.

This, to me, is one of the biggest problems facing our industry. In first year undergraduate in engineering we learn how to design a state machine. We learn to design one before we learned OOP and circuits and assembly. Yet, how many APIs or Protocols have you come across or has your organization developed where there isn't a state machine described somewhere. It may seem difficult and tedious, but this is how you engineer something rather than merely 'develop' it. We programmers sometimes spend far too much time juggling stuff in our heads and communicating with coworkers in a wonderful game of workplace telephone. If the state machine has become too complex, then we have lost all hope to fully manage it and must accept the risks. Some things just shouldn't be risked!

View on HN

I think one of the causes is that a lot of CS is taught top-down and not bottom-up, so things like flowcharts, state diagrams, and other similar visual aids are completely skipped in preference to more abstract thinking. I wonder if at least some of this aversion is directly related to the "gotophobia" that started with Dijkstra's famous paper.

It may seem difficult and tedious, but this is how you engineer something rather than merely 'develop' it.

As someone who learned the "old school" way of planning out your code --- yes, even drawing flowcharts and state diagrams --- before writing a single line of it, I can assuredly say that it should be a natural and completely pleasant process; what's "difficult and tedious" is trying to debug and coerce something you (or someone else) wrote without planning into working correctly.

Over the years coworkers have been puzzled at why I spend "so much time" flowcharting and just thinking before writing even a single line of code --- only to try adopting the same method once they realise how much time it saves in total, since all the cases have already been accounted for and the only thing left to do is test out any of the few remaining and often trivial bugs introduced during the design->code process.

It also takes all the "fun" out of programming, as so many seems to approach it like some grand display of mental prowess. Never mind the whole "agile" thing...

You can look at this both ways actually:

For some people (like me) thinking through problems with pen and paper is a tool.

For others I guess it is annoying: look at him, now he's doing this wannabe software architect stuff again.

Same might go the other way: here he goes again, trying to prove his programming super skills by jumping into it without even the smalles amount of planning.

FWIW I like to jump in and start coding, but what’s happening behind the scenes is that I “see” the algorithm or architecture in my mind. It’s not exactly a foowchart or a state machine, but it does have a sort of plastic manipulatable shape.

As someone who does both (flowcharts etc and exploratory coding) I think I experience something similar.

For me it is not very visual when I code. It is more a gut feeling: this goes here, that goes there. This is good, bad, weird but works etc.

This is nice for me but I know I have to work on how to explain it to others.

Bad example but I guess this is somewhat closer to what I want to be able to explain: "it currently works but it is a bad idea because it means you'll have to remember to patch seemingly unrelated functions x, y and z whenever you update this.

Also, in this case it is even worse as in the worst case you won't see the errors until the quarterly reporting run and that code is well known for having bad test coverage."

Edit: as usual I'm curious as to why parent was downvoted?

FWIW I don't think other people who jump in and begin coding are doing so blindly either. i.e. they do the same thing you do.

Everyone was presenting it as a dichotomy in this thread \_(ツ)_/¯

Seemed relevant to point out that at least for me it’s not.

Except at the highest level of abstraction, my Lucidchart diagrams and Google docs never survive their first encounter with the compiler. There always turns out to be some fatal flaw that's obvious in an editor but totally escaped me in the word processor. My (limited) experience has been teaching me the opposite: dive in as quickly as I can and write some code to explore the problem space, then go think harder about a design after getting my feet wet.

People are very different it seems.

I enjoy both diagramming and early exploratory coding.

I have real problems when one of my (really smart) colleagues wants to discuss some code we have neither written nor diagrammed yet.

For her however that seems to be the natural way of doing it and when we started working together I had to point out that just didn't work for me.

It seems to me that knowing and being aware and accepting of the different learning styles can solve a number of problems in teams.

>>There always turns out to be some fatal flaw that's obvious in an editor but totally escaped me in the word processor.

This problem goes away once you gain some experience - both in writing specs and in programming.

Think of it this way: do engineers build bridges without design documents and diagrams? No. So why are you writing software without them? If you aren't familiar with the problem domain, fine, do it the agile way. But once you gain experience there is no excuse to not thinking problems through in advance before trying to solve them.

It's faster and more pleasant to write working code than to write prose descriptions of hypothetical code.

Documents are cheaper to create and easier to change than bridges. Code is just another kind of document.

I've a sneaking suspicion that bridge building would look more like software if we could drive over AutoCAD models. (Or that software would look more like bridge building if we were still compiling by hand).

EDIT: I should add that I certainly do write and communicate documents about "what business problem does this even solve" and "what does it do" and "what are the major components and what are they responsible for" and "did you consider X alternative design" but planning down to the level of function signatures has usually turned out to be a waste of time.

Yeah, someone pointed this out to me once, and it is an interesting spin on the comparison of software engineering to other types of engineering. More succinctly:

We don't build our "bridges", our compilers/interpreters do.

The engineers don't build the things either, the construction workers do.

Sure, but it’s the construction work that you don’t start until you have exhaustive documentation.

>>Documents are cheaper to create and easier to change than bridges. Code is just another kind of document.

That really depends on the type of code you are writting.

Writing code going into a space craft, or Nuclear Power Plant, or Encryption code that can be relied on by people to protect their actual life, or code going into a medical device or.... you get the picture

Yes if your writing code going into the next Pokemon time waste game sure you can be fast and lose, but to not presume all code is the same.

In this instance, code is going into devices that historically do not get updated properly, I think that warrants taking a more "bridge building" approach and less "Code is just a document" approach

I think for that argument to work, you'd have to show that the word processing activity actually yields fewer errors in the resulting software. I guess what I'm saying here is that I've found writing prose beforehand to have low to zero ROI in terms of resulting software quality. I totally believe that writing math and actually proving things about your ideas would.

The more important code is, the more I want to see it subjected to a realistic and comprehensive test suite, careful peer review, etc. Although you're right, I ultimately work on backend systems that can cause some downtime at worst, not industrial process control or crypto libraries. I also have the luxury of doing continuous delivery, incremental rollouts, feature flags, staging environments with shadow traffic, etc. so there are a lot of safeguards standing between a mistake and widespread impact.

This is not specifically only a reply to you, but it seems like the two camps of "detailed specification on paper/word processor" and "code on the fly, because the code is a document" are missing a third alternative, which is TDD (ie, the tests are the specification), and a fourth alternative, which is literate programming (the code and specification are written together).

One can also use executable models, either in same language as the implementation, another general language with nice libraries or a DSL. For instance finite state machines

> I've a sneaking suspicion that bridge building would look more like software if we could drive over AutoCAD models.

Why on earth would you want bridge construction to be more like software engineering? Bridges work. We know how to build them bug free, every time. We don't know how to make working, bug-free software. There's even an old, not very funny joke about exactly this comparison. (Spoiler: it doesn't flatter the code monkeys.)

You might want to look up the Cynefin model[1]. Bridges are complicated, software is complex. This supports your bent towards experimentation, sort of; when solutions are unknown, that's required. But documentation and planning are part of what turns complex in to complicated, and that's a big part of the trick to successfully delivering big chunks of relatively bug-free code.

[1] https://en.wikipedia.org/wiki/Cynefin_framework

We have the mathematical tools describe everything that might happen to a bridge and determine how it will respond. Obviously that’s immensely valuable. Such tools are not available for handwavy descriptions of software in Word.

Your last sentence is actually kinda close to relevant to what I was talking about, but for the wrong reason. I suspect as your career progresses, you'll figure it out - most engineers do.

> This problem goes away once you gain some experience

As will the need for planning beforehand.

Code is just a detailed specification. A better analogy is that you start with designing the nuts and bolts without knowing how the beige is supposed to look.

Programming is the design. Building is performed by a compiler (free part).

Also, flowcharts are less readable than most programming languages in non-trivial cases. Graphical programming languages are mostly useful as DSLs. Text is unbeatable in the general case.

I once worked on a Finance project which had grand aspirations and decided it was going to Do Things Right by starting with extensive specifications.

The developers insisted on all behaviour being specified and documented before they would start coding. Of course, a truly exacting specification is equivalent to code. So the users who had been tasked with describing the required functionality ended up inventing their own DSL and “coding” the entire system in Microsoft Word.

Needless to say, they were the only ones who understood the spec. IT cried foul. Business cried “this is what you asked for!”

Cue months of arguments over what constituted a proper spec, during which the users essentially taught themselves how to code. The software eventually ended up being written by transliterating the DSL into actual code.

It worked, but remains to this day an unmaintainable mess.

> It worked

Congratulations!

Indeed, usually these approaches are abandoned due to reaching a point where arguments over specifications consume years and nothing happens. The project is killed and everyone involved are reassigned elsewhere, hopefully having learned something, but usually there's no such evidence of learning.

This is truly a great anecdote. I wish I could bookmark comments on HN, because I want to dig out this one when the time comes.

> I wish I could bookmark comments on HN

You see that "X hours ago" to the right of the username? Yeah, click that...

In all fairness, it's not entirely obvious that this is how to do it.

But it's a good tip nonetheless. Once you click the "x minutes/hours/days ago" link, besides bookmarking the resulting URL in your browser or elsewhere, you also have a few more options that show up at the top of the comment page. One of them is to "favorite" the comment. You can also favorite a submission in a similar way.

Just be advised that your favorite submissions and comments lists are public.

> it's not entirely obvious that this is how to do it

I totally agree that this is an example of insane, hidden functionality. How could anyone know that "click timestamp" = "view details"? Makes no sense.

However, seemingly every site/app has adopted this, from Twitter to Facebook to several PM services.

It's the only real 'title' of a comment beyond the user name, and the user name is already a link.

OK, so on HN, it's clickable. But "gray text without underline" isn't always clickable on HN. This is true of other sites: it isn't even clear that the timestamp is clickable at all, let alone what'll happen if you do click it.

Why not acknowledge that this is a problem and just add a little "Permalink" link, which some sites used to have? Or at least a permalink icon?

Surely the combined design talent of Google, Facebook, and Twitter can solve this problem better.

I think hidden is not quite the right word. It's a link, likely displayed in a hypertext browser.

A hypertext system that doesn't treat links as slightly opaque, explaining them in detail wherever they appear, sounds unpleasant to me.

I guess you could probably modify most such systems to have a flashing popup on every link that said "There is more information available if you click on the text here!!!!".

> It worked, but remains to this day an unmaintainable mess.

The question is: is it a worse mess than if you'd have started without the spec? My intuition says "no", and the experience the users gained regarding formal thinking is a huge net benefit that will be an asset for years to come.

So the documentation was simply incomplete, because the DSL, as a language, was not documented properly. This is why the initial developers were unable to have it maintained by others.

Essentially the same problem, just on a higher level of abstraction.

Oh, and failing to document DSLs is really a common mistake: No docs, no spec, no helpful error messages, and so on. Just like the very early parsers or compilers. But DSLs are really the most important thing to document, as these are so much harder to get into ... the "simpler" parts of the program are usually readable and understandable with less effort, even with pure code and no docs at all.

To those who downvoted: Do you care to elaborate?

What's wrong with demanding to document a DSL?

Well, the DSL flowed out of documenting the problem. Having non-technical people write a DSL, and then proceed to document that DSL, is not really addressing the core problem which was knowledge transferrence. Why do you feel they'd be better able to document a DSL than they were documenting the domain?

The whole purpose of a DSL is to make the whole system simpler, by separation of concerns.

That is, the DSL as a language is still much simpler (fewer data types, fewer elements, fewer rules, etc.) than the whole application, which is built using that DSL.

So I'd expect the DSL's documentation to be short and targeted at the people writing within that DSL.

If the DSL's documentation is more complicated than the original problem (spec), it failed at its purpose.

BTW, ultimately you have a chain of languages, such as:

    Spec <- DSL <- Meta-DSL <- ... <- programing language

But in the end, that chain goes from complex/specific to simpler/generic. So the documentation effort should shrink dramatically from one step to another (or your system design is seriously flawed). Usually, the Meta-DSL or Meta-Meta-DSL is already the plain, generic programming language you are using. And that one requires no documentation writing at all, because is already documented and widely understood.

I am not a programmer. I have done a lot of programming. Eventually, I was able to hire competent professionals. I have taken very few formal courses in programming and zero in what I'd call computer science. I programmed out of necessity. Computers were pretty useless if you didn't.

So, take this with a grain of salt.

I can't code without a diagram. I make a diagram and process the logic. I make lots of sub diagrams. I make notes and ask myself a lot of questions. I'll also ask other people, if I can.

I can't do it. I can't program 'on the fly.' My attempts have resulted in horrible results, not even qualified to be called results. If I don't process the logic, pretty much from start to finish, I can't do it. I use a notation system that isn't even a real programming language and leave lots of room to cram more stuff in and make corrections.

Most of this is past tense, I don't do much anymore. I'm retired and my efforts are just little automation tasks for my own needs.

Anyhow, I figured I'd offer another perspective/opinion. I envy you if you can do it off the cuff. I've tried, I can't.

I have a CS degree and a few years professional programming

I have coded on-the-fly and I have coded from diagram first approaches.

on-the-fly works for me when there is an obvious data structure to work to, otherwise it takes a lot longer than planning it out because of all the edge cases

Data structures and ADTs are the key in general.

I think it depends on thinking style and mental models. Personally I have "diagram blindness"; most diagrams look like visual noise. Usually I get better (fast, reliable, maintainable) results by just coding on the fly and then relentlessly refactoring as the optimal design gradually reveals itself.

If you consider the diagrams as a physical manifestation of abstractions that can eventually be converted into boolean logic, etc than it's the same thing. For many years I used to draw on paper a mix of non-standard diagrams with some pseudo-code to discuss slightly complex algorithm implementations with peers... the more coding experience you have, the less you need to do this and you usually make the connections just in your brains and start coding.

So my tip here is if you want to learn how to do it on the fly you should start with small steps by reducing the amount of stuff you need to see in a paper before start coding. In the other hand it's perfectly normal and there is no problem in doing what you do.

When I program 'on the fly' I either have the diagram in my head, or I'm working 'linguistically' such that things are correct-by-construction / facts about objects are true because-of-what-they-are rather than because of what they do. For example, using std::shared_ptr to manage a resource instead of trying to reason out all the cases to manually free the resource. I guess what I'm saying is that rather than thinking about all the cases to see that the code does work, I try to write code in a way that it is not possible that it does not work.

Isn't this where formal specification languages like TLA+ are useful?

yes

I sometimes describe TLA+ to people as "unit-testable flowcharts." It's pretty inaccurate but kinda gets the idea across?

Thinking in state machines is not the same as design up front. Most languages lack a good way to describe state machines, but there are many libraries which do this and even produce the diagrams for you (which can be very helpful when trying to understand the code). I frequently write state machines in an incremental manner.

Enums (or named constants if you don't have enums) and switch statements (or if you don't have these, make a hashmap of state->method or something) are all you need. I'm not sure I get what you mean.

One of the primary features of state machines is that state transitions are well-defined. "Describing state machines", as the GP said, is typically done with tools like a reachability matrix or truth table. A looped switch statement will allow you to implement a state machine, but not describe it.

In other words, how would you express in code: "state Z can only be entered through either state W or X, but not through state Y", or "state V must be followed by state W, but only after condition A"? Sure, you can write a switch statement. But half the rules of a state machine can only be implemented by omission (i.e. by not coding it, instead of hardcoding the requirements).

Do you keep your documents up to date? I will occasionally sit down and diagram how I want everything to work usually in a simplified UML diagram, an FSM diagram, or a sequence diagram. It certainly makes initial development faster.

But then the changes start and now I either discard the diagrams or accept that I have two things to maintain. Generally I take the former path because divergence from the plan is almost inevitable on anything that's alive.

You do realize how bizarre it is to blame lack of rigor in CS on the author of "On The Cruelty Of Really Teaching Computer Science", right?

http://www.cs.utexas.edu/users/EWD/ewd10xx/EWD1036.PDF

pseudocode and application logic is absolutely necessary. Visualization is cumbersome and unnecessary except in large codebases.

I usually hack out something fast to understand the issues (there will always be issues) and reiterate by modifying old code to the new func/api which allows me to find corner cases.

I find it interesting how in a large codebase or project there is a temptation to mutate an object here, decorate some intermediate object there, and before you know it you have an ugly state machine hiding in your code. As you know the number of possible states grows very fast and when people don't know this is happening things soon get out of control. Having things immutable by default helps somewhat, but it's still easy to add various decorators.

> there is no formal description of the 802.11i handshake state machine.

Here is what the paper actually says:

The 802.11i amendment does not contain a formal state machine describing how the supplicant must implement the 4-way handshake. ... Fortunately, 802.11r ... does provide a detailed state machine of the supplicant.

The problem, as I understand it, was that when the protocol was formally verified, the properties checked were only the escape of the private key and identity related issues. The property of the nonce never being reset was simply not considered.

The missing piece, then, wasn't a precise description of how the system works, but rather a precise list of what it's supposed to guarantee. Without a clear and concise description of the requirements, it's hard to verify that the system satisfies them. Alternatively, it's possible that the list of guarantees was complete, in which case reviewers should have noticed that no nonce reset isn't one of them, yet it's required for the security of certain communication protocols used over the channel.

I guess a related question would be, is anyone aware of a common protocol that does have a formally defined state machine to review?

TCP's might not be formally defined (unsure), but it's pretty well understood to the point of having de facto ones, at least.

There are state diagrams in the TCP RFC --- in ASCII art, so the authors clearly really wanted to have one.

Nice! Good to know.

That must be the origin of all the useful but unofficial SVG ones I'd seen :)

SSL

Here is really cool work on state machines in TLS: https://www.smacktls.com/smack.pdf

Beurdouche et al., "A Messy State of the Union: Taming the Composite State Machines of TLS"

From the abstract: "mplementations of the Transport Layer Security (TLS) protocol must handle a variety of protocol versions and extensions, authentication modes and key exchange methods, where each combination may prescribe a different message sequence between the client and the server. We address the problem of designing a robust composite state machine that can correctly multiplex between these different protocol modes. We systematically test popular open-source TLS implementations for state machine bugs and discover several critical security vulnerabilities that have lain hidden in these libraries for years ..."

Based on this work you might say that there are formal state machines for TLS, but they aren't in the standard.

HTML parsing is, from the HTML 5 spec onwards, defined as a state machine.

JSON, but it isn't that pretty.

JSON is actually not well or consistently specified, and definitely not to the rigour of a state machine; it’s specified in half a dozen places and ways, with inconsistencies and fuzzy details; see http://seriot.ch/parsing_json.php.

RADIUS.

When we designed DCCP, I did a formal model using LTSA to prove liveness and safety properties. Mostly I did it for fun (I got landed with teaching concurrency, and the previous professor had used this tool). As formal models go, LTSA is rather simple. I was pretty surprised when it found a previously unknown deadlock state. To my chagrin, a decade or so earlier, I'd observed a very similar deadlock in the Solaris TCP stack when running SMTP, which is unusual in that it requires the server to send first.

I shared the LTSA model with a few others at the time, but no-one else seemed very interested in doing anything with it.

https://www.doc.ic.ac.uk/ltsa/

https://tools.ietf.org/html/rfc4340

Edit: I dug through my old backups, and I think this is probably the model I used:

http://nrg.cs.ucl.ac.uk/mjh/dccp.lts

It's nothing fancy, but my point is that even simple modelling can spot errors that a whole standards group of smart people miss.

Compare front-end [1] design philosophies (such as used in waterfall development) vs iterative design philosophies (such as in agile development). As a non-software, 'real world' engineer (mechanical, heavy industry design) looking in from the periphy of computing as a hobby/amateur interest, it appears to me like software engineering as a discipline has sort of forgotten about why and when FEED is appropriate and, critically, how to implement it when it is.

Let's reflect: iterative design is popular in software engineering because software usually suits it. Changes are easily iterable, you can often roll changes back, there's relatively low cost to cloning changes across millions of instances, code's design lifetime is relatively short, etc. In contrast, 'real world' engineering (civil, heavy mechanical) favours FEED because the cost of change rapidly and prohibitively rises with time, so nailing down the scope and structure early is critical, there's long procurement times for changes, the design lifetime of the finished product is measured in decades, etc.

The rub is that there's a small niche of software design, such as protocol design like this, or certain firmware scenarios, which far more closely resembles the latter even though it's usually done by a community used to and trained in the former. Although it's for different reasons, all the things that make FEED appropriate for 'real world' engineering also apply to these sorts of software tasks, but software engineering as a whole doesn't appear to[2] focus on teaching and supporting the necessary tools and techniques for performing that process well.

Flip that on its head, and it's why software companies quickly begin to run rings around companies traditionally focused on hardware once software starts to play a bigger part and the limitations stopping iterative design from working begin to disappear. Software engineering largely biases towards iteration (understandably) and when it works it allows for good advantages. But in embracing those advantages, software engineering as a discipline has begun to lose an understanding of FEED and the careful methodology it delivers.

[1]: https://en.wikipedia.org/wiki/Front-end_engineering & https://en.wikipedia.org/wiki/Front-end_loading

[2] I admit I've not done a CS/SE degree, but I've gone through a couple of subjects run online and I talk to friends who did do it and that's the feel I get. Besides, just look at HN's generally trending articles.

edit: With all I wrote, I don't mean to undermine the extremely good work that the devs designing these protocols, etc. almost always perform. It's far beyond my ability. I am speaking more in a general sense about how Soft. Eng. seems to have thrown out the baby with the bathwater in declaring agile philosophies as 'the best way'. My feel is that the pendulum seems to have swung too far past 'best' towards becoming 'only'.

> It may seem difficult and tedious, but this is how you engineer something rather than merely 'develop' it.

Don't agile approaches encourage this, focusing on features and things that can cleanly be assigned story points at the expense of a bigger picture, with velocity being the focus?

It seems to me that agile approaches are a response to the phenomena of the spec often being wrong. If the spec is wrong and going to need substantial revision, iteration is better than planning.

If the spec is not wrong, careful planning is probably better than high velocity iteration.

I think cryptography is a good example of this--would you develop a cryptographic API on which people's lives might depend iteratively through a release early and fail often method? I hope not.

Exactly, and this is why Agile (while grand for things like "The customer wants a web site. They don't know what they want or how they want it to look, but we need to start on Tuesday.") isn't the be-all and end-all that it's advertised to be by people who only work on websites for tech-illiterate customers.

In a lot of software development, especially large scale enterprise software (where you're trying to map a complex set of existing business practices and workflows into software) and embedded software (where you have to write something that provides fixed, well-understood functionality running on hardware with a months- or years-long iteration time) you do have a complete and correct spec (or at least the means to generate one). In these cases a less ad-hoc approach than Agile can be beneficial.

I upvoted this, but agile and "release early and fail often" aren't necessarily the same thing. For example, they could have iterated quickly during the draft phase, come up with a proposed implementation, have the security researchers review it, and iterate.

Either engineering and its tools (eg state machines) or just craftmanship.

Totally right.

It is tedious. It’s inefficient. Quality software usually is less important than working software.

Unless I'm misinterpreting the meaning of "usually" or "important", I find this comment a little bewildering in the context of the article.

In the working world, what matters is you ship. The most beautiful code and best "game ever designed" means nothing if it doesn't ship.

Additionally, in my years of working as a contractor, I can tell you that nearly 1 in 1,000 companies (+ or - 1) care about security. Management simply does not value it, and everyone already thinks your product "should have been done yesterday." The entire world runs on insecure products. From banks, to healthcare, to universities. I can list every one of those who has put admin credentials in a publicly, internet accessible text file. (But they'll do silly things like insanely unmemorizable passwords like 23ix2n5 that get written down as postit notes and as files on desktops, and disable RDP copy-and-paste but leave RDP hard drive support.)

We're going to continue seeing these blunders day after day until people start going to jail for losing data.

Or stop treating programming like some grand joust...

We won't. Worse is better, remember? Especially when a typical company wants to be the first to quickly sell some shit product and then, maybe, they'll patch it for a while as they go along. Competitive pressures (and management fads, IMO - software market ain't that efficient yet) turned "good solution today > perfect solution next week" into "steaming pile of garbage today > good solution tomorrow".

I guess this is fine for throwaway acquihire SaaS stuff, but it's becoming a serious problem for stuff that's meant to be widely used.

Consider it descriptive rather than prescriptive.

Can you think of any particular circumstances where quality would be of paramount importance?

I'll wait.

Pacemaker firmware comes to mind.

You’d think: https://arstechnica.com/information-technology/2017/08/465k-...

I've been working in the same code base one way or another for more than 20 years now. Quality is underrated.

Reply on news.ycombinator.com