Is it possible to prove mathematically that a server is immune to denial-of-service attacks? Or is there some result in computer science journal that it this is an impossible task to do?
-
Cannot prove negative. This includes, but is not limited to, server security against anything.– fraxinusCommented Apr 11, 2022 at 13:09
-
Proving a positive is just proving an oppositely-stated negative, and vice-versa. So you can absolutely prove a negative. In particular finite models of computing, you can prove that a program does not halt, for example, which is quite comparable to this question.– Matthew ReadCommented Apr 11, 2022 at 20:08
Add a comment
|
3 Answers
You cannot be immune to Resource Exhaustion
It's fundamentally not possible. Every server or cluster of servers has a maximum amount of workload. If an attacker is capable of exceeding that, then you will not have enough to serve your intended customers and thus you have a Denial-of-Service attack.
For the sake of clarity, "resource exhaustion" is one form of Denial-of-Service, but there are several more. For example, I could abuse a vulnerability in your code to crash your server repeatedly, lock all customer accounts, use shaped charges to breach the walls of the datacenter and then go wild on your servers with a shotgun, etc... All of these would result in "Denial-of-Service" in one form or another, but their mitigations are very different.
My point is that you cannot mathematically prove to be immune from Resource Exhaustion, because no one can be immune. Nor can you provide proof to be immune from someone physically destroying your servers, etc...
Provable security is possible - to a degree
Provable Security refers to some form of mathematical proof, which ensures that a certain product ensures it will do what it claims to do. The seL4 microkernel, for example, has some proof that some functions do what they claim to do (although that doesn't mean it is impossible that the hardware used to run it has no vulnerabilities).
However, trying to prove that a microkernel does something and trying to prove than an application does something are two vastly different tasks, because an application depends on so many layers below, that it becomes functionally impossible.
-
9Provable security is typically about ensuring the correct execution of a program, and the confidentiality and integrity of data. It's typically not about availability — in a formal context, this is typically studied for real-time systems with safety requirements, not for security requirements. Commented Apr 8, 2022 at 14:10
-
2I disagree with this. I can think of a cryptographic construction that would allow legitimate clients to be able to connect without allowing anyone else. Authenticated Hidden Services for Tor HSv2 is an example of that. Without access to the authentication cookie, you cannot even find the server, much less DoS it.– forestCommented Apr 8, 2022 at 22:08
-
5It seems to me that it could still be useful to provide proof of security against resource exhaustion by a specific adversary. That is, a statement to the effect of "we would be available at or above specification against an adversary up to 1000 times our compute capacity" could translate to "we're secure against the top three botnets working in concert" without having to claim to beat a hypothetical star sized alien supercomputer.– JosiahCommented Apr 9, 2022 at 6:13
-
3@forest HSv2 is only provably secure if Tor is proven secure (it can’t be proven secure without assuming certain constraints which can’t be verified in real life, at least for the public Tor network) and the node and service being masked by it are secure. And even then, it only protects the node against DoS attacks on that specific service by untrusted users. Commented Apr 9, 2022 at 19:20
-
4@forest do note that DDoS is a form of DoS, and it quite often relies on horde of compromised legitimate clients to do the attack. In a same way, a horde of compromised clients which has access to that hidden service will be able to DDoS it. Another option is DoS-ing underlying TOR infrastructure, thus bringing said TOR hidden service down (along with the rest of the onion network). Commented Apr 9, 2022 at 23:30
Yes, disconnect it from the internet ;)
Seriously though, even if you properly scope your resources to handle "legitimate" requests, and also somehow guarantee that you only need to do the most minimal amount of work to determine whether any packet of data is "bad" so you can ignore the contents, attackers could still flood you with enough "bad" packets that "legitimate" traffic is processed more slowly or not at all.
-
1What about a server that is not connected to the internet but a private network? If the private network somehow had a known maximum number of communication generated by all machines, then maybe you could prove DoS is not possible.– qwrCommented Apr 8, 2022 at 22:21
-
5Disconnected from the internet is no guarantee of of security Commented Apr 8, 2022 at 22:23
-
2@noslenkwah it was more a joke for the OP's benefit. The point of the joke is to say that one (very impractical way) of preventing denial of service is to provide no service to anyone ever for any reason, but of course that is essentially also the definition of service denial ;) Commented Apr 8, 2022 at 22:25
-
1Disconnecting your computer from the internet in order to prevent a DoS attack is like burning your house down to stop an arsonist from doing it. Commented Apr 10, 2022 at 14:52
-
1@noslenkwah Isn't acoustic data transfer just a different and rarely-used network transport? Could be considered part of the private network that you need to disconnect systems from.– doneal24Commented Apr 11, 2022 at 16:06
In practice? Absolutely Resounding NO.
In theory? yes. To wit:
- step 1. you can use formal methods to mathematically evaluate every possible combination of states your program can ever take, and amount of resources it uses in the worst case. (Note that this gets hugely expensive really fast the more complex your program is, but is theoretically doable, if the universe lasts long enough and you have enough computing resources to throw at the process. So, as prerequisites, make sure service provided by your server is extremely simple, that you are preferably immortal, and that your patience is astronomical)
- step 2. when you have calculated the worst case resource usage, you simply make sure that you have more resources available for your server than all the rest of the universe combined (as we'll surely be way more than just multi-planetary species by then) can throw at you. Might be somewhat costly and tiresome to implement too (but those are just economic and engineering details, not worthy the attention of pure theorist)
- step 3. profit.
Summary: given that you asked this on security.SE and not math.SE:
No, it is not possible to prove that a server can be secure against DoS.
-
@user253751 You seem to underestimate the vast meaning of "every possible combination of states". That collection of state combinations already include "how many computing resources does the rest of the world have at any given point in time".– orithenaCommented Apr 11, 2022 at 11:03
-
@user253751 You seem to be trying to get a point across here without explicitely telling it -- or rather: I can see multiple points in your comment, but none that I don't see covered by the answer.– orithenaCommented Apr 11, 2022 at 11:13
-
1I love that the first step is, in practice, basically to DoS yourself by dedicating absurd computing resources to evaluating the concern, which could potentially instead be added to the computing pool to help prevent the resource exhausition by DoS Commented Apr 11, 2022 at 18:52