Everybody makes mistakes when writing comparison functions

https://karpov2007.medium.com/everybody-makes-mistakes-when-writing-comparison-functions-9cd49ea35088

by ingve • 5 years ago

62 62 5 years ago

karpov2007.medium.com

enlyth• 5 years ago

The author's article about comparison functions linked in the blog post is worth the read

Regarding the OpenSSL example presented here, wouldn't any decent IDE catch an unused parameter in a function? Why is a separate static analyzer necessary for this

wwn_se• 5 years ago

I think the point is if you integrate the analyzer in the workflow its hard to ignore. The ide warnings are easy to miss sometimes.

tialaramex3• 5 years ago

The Right Thing™ for a project that actually has multiple contributors is that the CI pipeline rejects code that based on the compiler diagnostics is either definitely wrong or, if it was correct, should be annotated in a way the compiler can understand and stop emitting the diagnostic. It doesn't matter whether one or another contributor has this switched off or ignored it.

That is, committing this code should have had the same impact as if it was missing the semi-colon, the library doesn't build, tree is on fire, fix before you do new work.

Of course if your code is in sufficiently bad state, you might find it's frustrating to have say 500 bugs to solve before you can get the CI pipeline to output artefacts. I think that means you didn't have good software and you must fix those bugs first, but if you're convinced the software is good it can be tempting to instead disable the diagnostics telling you otherwise and press on.

You have 178 seconds to live:

https://www.youtube.com/watch?v=b7t4IR-3mSo

jraph• 5 years ago

Why is a separate static analyzer necessary for this

Because this is a nail this co-founder of PVS-Studio saw while holding the hammer he wants to sell.

By the way, it seems to me this error does not have much to do with comparison functions, it is a mistake that can be made in many kinds of functions.

Unused parameters are warned against in C (hence all the UNUSED macro hacks) and no static analyzers are going to save you if you don't address compiler warnings, they are just going to add more warnings to that pile of warnings you already have (or maybe don't get because the right warnings are not enabled).

(I'm sure their blog is full of cases a static analyzer would handle which compilers won't warn you for though)

Still surprising to see such an error in OpenSSL and like others here I would be interested to know why it was not caught.

choeger• 5 years ago

I think comparison functions are a prime "use case" for this kind of error because it will pass the type check easily and comparison is often somewhat symmetric, so you will do a lot of copy and paste. Only unit or property tests could catch this (and a compiler warning, of course). The example here is of course extreme, but I bet you will find something like this quite often, especially in OO code like Java.

NohatCoder• 5 years ago

Last time OpenSSL was in the news for a bug that should generate a warning I took a cursory look at some of the code, it was stuffed with stuff that would generate similar warnings. So at that time I concluded that going through all the warnings would be a pretty big job, and that is likely why nobody did so. On the more speculative front, it might be that some maintainer is against taking whitespace patches, that would probably make anyone who tries give up pretty quickly.

I'm a bit skeptical of the claim "The code quality is excellent", if it was this would be a lone warning emitted by the compiler, and surely it would have been fixed then.

umanwizard• 5 years ago

A lot of people don’t use IDEs to write C.

That said, I believe the two mainstream C compilers (GCC and Clang) can both be configured to emit a warning here.

PVS-Studio3• 5 years ago

If a diagnostic issues warnings to unused arguments - it's a weak diagnostic. PVS-Studio acts differently. Take a look at my clarifying comment below or above (not sure where it would be when you read it).

stinos2• 5 years ago

Unused function argument is a warning any sane compiler can spit out and turn into a hard error (so this is not really the best example of what PVS studio can do for you), which makes one wonder: why was this not caught earlier? Warnings not enabled, or ignored, and is that something which is problematic wrt something as major as OpenSSL?

misnome• 5 years ago

I also wonder this. "Unused parameter in function" is one of the most basic warning/linting checks. I'd be interested in finding out how this managed to reach release.

pabs3• 5 years ago

Both GCC and clang warn about unused parameters, but only when you run them with -Wextra.

coldpie2• 5 years ago

Having unused parameters is super common, especially when using function-pointer-based APIs like qsort. Arguably they should have annotated the arguments to suppress the warnings, but that starts to get into compiler compatibility (OpenSSL is used on a _lot_ of systems with a _lot_ of compilers) and becomes a much larger question than just setting -Wno-unused-parameter.

PVS-Studio3• 5 years ago

So I want to add an explanation. As I see from the comments, many of you thought that the PVS-Studio analyzer warns about a function's unused argument. That's not quite so. Or, to be precise, this is so, but the analyzer processes this case smarter than most linters or compilers.

It's a bad idea to program an analyzer so that it just issues a warning to unused arguments. Such analyzer would produce many false positives, which is why many developers don't look at (or disable) these warnings in their compilers/analyzers.

The PVS-Studio analyzer implements sort of empirical "magic". PVS-Studio relies on the fact that there are arguments of the same type and some of them are not used, while the other ones are used several times. At the same time, there are a number of exceptions to the rule. For example, the diagnostic is not triggered if the number of unused arguments exceeds two.

All this allows the V751 diagnostic to issue few false positives, which makes the tool surpass its competitors. To be exact, when developing PVS-Studio, we do not implement rules if we cannot make them better than those of the compilers - https://pvs-studio.com/en/blog/posts/0802/ . Thanks to the diagnostic I described above, one can find interesting errors - https://pvs-studio.com/en/blog/examples/v751/ .

P.S. The PVS-Studio analyzer also provides a "stupid" version of this diagnostic - V2537 https://pvs-studio.com/en/docs/warnings/v2537/ . It was developed to check code against MISRA C and MISRA C++ standards. But the case above was special and by default this diagnostic was disabled - same as the other ones related to MISRA.

ajuc• 5 years ago

My favorite thing about Clojure is that comparison functions work on any number of arguments and correctly test equality of nested data structures.

wbazant• 5 years ago

I like comparing how different birds interact with each other in the park. Some flock in little groups, but the ducks swim around the park pond.

kleiba• 5 years ago

Everybody makes mistakes writing any kind of function.

junon5• 5 years ago

God I'm so tired of this take. "All code has bugs." "Everyone writes shitty code, some just make it less shitty." ad nauseum.

I don't know where this started (more, when it got popular) but it's such a cop out and lazy argument to anything safety-related.

It adds nothing to the discussion and provides no insight or substance, yet people parrot it often, especially around "language lawyer"-type HN articles.

Moreover, it's wrong. Not every function has a bug. Yes, there are ways to prove this. No, not every function needs to protect against the computer being struck by lightning, or any other fault, in every case. It's such a weird and wrong argument and it's always said with such confidence.

sethammons• 5 years ago

The idea that all software is terrible or all code has bugs is leveraged at my work as a form of psychological safety. "Yes, 'all' software has bugs, so you should feel safe exposing a bug you made and we can all learn from it." A person who took the saying as an excuse to be sloppy would get called out hard on our teams and wouldn't last if they kept that view.

Levitz• 5 years ago

I think every code has bugs in the same way that every gun is always loaded. Yes you can throughly check for it in some place and be rather sure that it's not loaded, but the way to act around it is as if it could always be loaded.

This doesn't excuse writing buggy code, same as you should always handle a gun with care, but it promotes good behaviour around it.

jusssi• 5 years ago

You can formally prove that a function always does exactly what the author intended, no less, no more. But it still might be the wrong thing to do. The question is, do you count that as a bug or something else.

commandlinefan2• 5 years ago

Not every function has a bug

Ok, you're right. Every non-trivial function has a bug.

wiz21c• 5 years ago

I know it's a bit futile, but according to its name the function seems quite generic. So I guess it's used in various places, so I wonder how such a big (in consequences, not in lack of attention: I code all day long I make tons of mistakes myself; been there done that got the T-shirt) mistake could still be there... (I repeat: I don't blame the coder, I know the stuff, I just honestly wonder)

blunte• 5 years ago

Most linters and editors would highlight this. Also, if one writes test, one of the test cases should fail.

This is just a typo, not really a quality ad for some code quality monitor.

ChrisMarshallNY2• 5 years ago

I have a friend that used to be an OpenSSL contributor (not sure if he still is). Not really a big deal. There were a lot of them.

He was generally cranky ["curmudgeonly"? -Ed.] about the code, and tried submitting quality fixes, where possible; but this was years ago.

PVS-Studio looks great. I wish it worked on Swift. SwiftLint has its limitations.

petee• 5 years ago

I was surprised to read in the article that the code quality was good, unless they some how pulled off a major refactor since LibreSSL basically called the code a mess.

If I recall, the claim was that OpenSSL prioritized issues paid for by companies, and the alot was left to rot. I'm curious if your friend saw the same things?

kreetx• 5 years ago

There is a difference in when a tool considers code to be of high quality and when humans do.

ChrisMarshallNY2• 5 years ago

I have never gazed upon the code, myself, so only have thirdhand anecdotal information.

He didn't speculate as to "why," but he said the project was very buggy, and rather "messy."

To be fair, we worked for a company (he was one of my employees) that was anal about Quality, and hard to please. It rubbed off on us.

IncRnd• 5 years ago

OpenSSL 3.0.0, which is what the article mentions, is a new version that is incompatible with older versions of OpenSSL. its internals operate in a completely different manner. It is a very changed codebase. That being said, I would not say its code quality is good, regardless of whether any tooling reports that.

macksd• 5 years ago

The author links to a much more detailed list of mistakes in comparison functions. It's worth reading: https://pvs-studio.com/en/blog/posts/cpp/0509/

dhosek• 5 years ago

I have to admit that I was expecting this to be about some subtle and often overlooked logic error in writing comparison functions (say assuming that a ≮ b ⇒ a > b). But this is about what essentially amounts to typographic errors in the code.

OneEyedRobot2• 5 years ago

On a related note, I think the most errors I've seen in sizable C++ systems has been operator overloading for things like '=' and '=='. Too much hidden magic can occur.

jeffbee• 5 years ago

If you don't override or explicitly delete them you get compiler defaults, which are even more magic and harder for the reader to reason about.

OneEyedRobot2• 5 years ago

I agree, and I think it's probably a good idea for any class that isn't a simple structure with functions.

I suppose that a problem with C++ (and the more feature-filled source control systems) is that it's dangerous to mix different levels of programmer sophistication in a team. The people are reflected in the code particularly as the obfuscation increases.

martincmartin• 5 years ago

The mistake I often see in interviews:

    int cmp(int a, int b) {
        return a - b;
    }

This can easily overflow or underflow. For example, if a = INT_MAX and b < 0.

I don't count it against the person interviewing, because its common and arguably reasonable if your values are all < INT_MAX/2.

HarHarVeryFunny• 5 years ago

I don't see how that's specific to comparison functions. It's just a result of someone not unit-testing their code.

I was expecting to see an example of structure comparisons such as struct date {int year; int month; int day;} which are easy to get wrong unless you've internalized the pattern (or use modern C++ where it'll generate the comparison operators automatically for you).

AndreyKarpov4• 5 years ago

The main specific is that it’s one of the most common errors. People don’t check comparison functions, but those functions have errors. You can read more here: https://pvs-studio.com/en/blog/posts/cpp/0509/

brabel• 5 years ago

As someone used to tools like IntelliJ for Java and Kotlin, and Clippy for Rust, this is like the most basic kind of warning I can imagine.

It blows my mind sometimes what IntelliJ, in particular, catches... like code branches that can never execute due to intricate conditional blocks in the same block of code... forgetting to use a method argument is not even worth a mention :D

Look at just how many issues IntelliJ can detect for Java: https://www.jetbrains.com/help/idea/list-of-java-inspections...

AndreyKarpov4• 5 years ago

Unfortunately, I don't fully understand your comment. PVS-Studio has a variety of diagnostics. However, such simple errors still exist. By the way, PVS-Studio found errors in IntelliJ IDEA as well :) - https://pvs-studio.com/en/blog/posts/java/0603/

yegle• 5 years ago

I was a bit disappointed when the focus is not related to cryptography.

I.e. a poorly written comparison function compares multiple expressions and the use of && short-circuit the logic, result in a timing attack.

Would love to read an article about this topic, i.e. how to write a function whose execution time is constant regardless of the inputs, and thus not leak any side-channel information to the attacker.

AndreyKarpov4• 5 years ago

I agree, it’s a bit of one-sided point of view. It’s only about the code quality. The cryptography analysis is beyond static analysis tools’ capabilities. Static analysis is more high-level study.

PVS-Studio3• 5 years ago

Everybody makes mistakes when writing comparison functions

Related Stories