14
\$\begingroup\$

Robber Thread here

The Challenge

Choose any numeric* formula, algorithm, or code challenge. Implement it in such a way that the math is correct, but at least one answer is wildly** wrong due to some defect in how computers/programs operate, e.g. floating point errors, uninitialized/corrupted memory, environment bugs, compiler optimization bugs, library bugs, weird language features, etc...

The domain and range (i.e. inputs and outputs) of your formula must be well-defined.

Requirements

Your challenge must include the following:

  • The formula / algorithm / code challenge
  • The source code of your program / function
  • A well-defined specification of the domain and range of the program
  • A precise description of how wrong a particular answer is:
    • Whether it is incorrect deterministically or not- and how often it is incorrect
    • A numeric description of how wrong the returned answer is relative to the expected answer. This could be:
      • in absolute terms (e.g. off by at least 1 million)
      • an order of magnitude (e.g. 1000x larger or smaller)
      • relative to the inputs (e.g. off by more than half the value of the larger of two inputs)
      • some other reasonable measure of error (e.g. correct except for the sign, vector components transposed, rotated by 90 degrees on the complex plane, etc...)
    • A vague estimation of how many outputs of all possible inputs are affected by the error.
    • (if the output is a list, tuple, or matrix) The number of elements affected by the error.
  • An environment setup (OS, libraries, language version, runtime, compiler and relevant flags, etc...) which reproduces the error.
    • Include a link to the specific version used for compilers, runtimes, languages, and libraries.
    • You may link to a Docker image or Dockerfile of your environment. Although this is not required, it would be very kind to do so if the environment that causes the numerical error is very specific.
    • Try to keep the set of libraries in use small.

The robbers will be trying to find an incorrect answer and explanation why it fails. Your formula implementation will be considered "safe" after 7 days.

Example

Cop Challenge

  • Formula: The Pythagorean Theorem, \$ a^2 + b^2 = c^2 \$
  • Inputs: 2 nonnegative real numbers
  • Off by more than either input number
  • Affects most inputs
  • WSL (Ubuntu 18.04) on Windows 10, Python 3.6.9
def badpythag(a, b):
    a2 = (a / 1e200) ** 2
    b2 = (b / 1e200) ** 2
    return math.sqrt(a2 + b2) * 1e200

Cracked Answer

This will fail on many inputs (e.g. 3, 4 => 0, but should be 5) due to floating point underflow and return 0. The answer is correct with very large inputs e.g. 3e150 and 4e150, however.

Rules and Scoring

  • Score 1 point if your challenge remains uncracked after 7 days.
  • You can submit multiple challenges to the cops thread.
  • Incorrect answers do not need to be deterministically wrong as long as they are wrong more than half of the time (a broken clock is right twice a day).
  • Abusing undefined behavior is fair game.
  • The error should not be hardware dependent. Not everyone has a Raspberry Pi, let alone some obscure model of the x86 with a specific floating point bug.
  • GPU code is not allowed. There is too much variance in drivers and graphics cards for this to be a reasonable point of exploitation.
  • Caveats on libraries:
    • Errors caused by libraries must be the result of a known and documented flaw. The flaw must have been documented no later than a month before the posting of your cop challenge.
    • You can use old versions of libraries as long as they are publicly available from a reasonably trustworthy source at the time your challenge is posted.
    • Libraries you use must be free for noncommercial personal use and publicly available.
    • Libraries do not need to be open source.
  • You can use old language versions (and compilers) as long as they are publicly available from a reasonably trustworthy source at the time the challenge is posted.
  • You may exploit compiler and runtime bugs.

* By numeric challenge, I mean anything with a domain and range which consists entirely of numbers, tuples/lists of numbers, lists of lists of numbers, vectors, matrices, etc... Complex numbers are fair game. Numbers may use any representation.

** What is considered wildly wrong depends a lot on the scale of the domain and range of the formula/algorithm. What would be wildly wrong for particle physics is a rounding error for walking around the block, while a rounding error for galaxies might be off by a planet or two when trying to find someone's apartment. Yes, this is inherently subjective, but this is why your challenge must define a specific numeric definition of exactly what you consider wrong enough to count. As a general rule of thumb, to be considered "wildly" wrong, answers should be off by at least an order of magnitude (preferably more), be zero at the wrong time, have the wrong sign, or something else equally nefarious. It should generally be the kind of error that might lead to someone's death if it were to be integrated into medical software rather than something that causes the patient to wake up a little early, while the surgeon is tying up the last few stitches.

\$\endgroup\$
2
  • \$\begingroup\$ Am I correct in understanding that all uncracked answers score equally? \$\endgroup\$
    – Wheat Wizard
    Jan 15, 2021 at 8:57
  • \$\begingroup\$ @WheatWizard that is correct. I may revise that to incentivize new challenges, but I'll see where this goes first. \$\endgroup\$
    – Beefster
    Jan 15, 2021 at 16:25

4 Answers 4

6
\$\begingroup\$

Python 3 + sympy, cracked by water_ghosts

This is a primality checking function. It returns True for primes, and False for non-primes.

from sympy.ntheory.primetest import mr
from sympy.ntheory.generate import primerange

def is_prime(n: int) -> bool:
    if n < 2: return False
    return mr(n, primerange(2, 800))

Find a composite number that is falsely declared as prime. There are infinitely many solutions.

You can try it online here. As far as I know, the solution works for any modern version of Python/sympy, no specific environmental setup is required.

\$\endgroup\$
4
  • \$\begingroup\$ Did you ever know a single valid solution to this program? \$\endgroup\$
    – tsh
    Jan 15, 2021 at 2:09
  • \$\begingroup\$ @tsh yes, I have a solution \$\endgroup\$
    – Sisyphus
    Jan 15, 2021 at 2:11
  • \$\begingroup\$ Cracked \$\endgroup\$ Jan 15, 2021 at 6:44
  • 6
    \$\begingroup\$ I think this post perfectly fits the spirit of the challenge. However, it's more like "The answer is correct, but the math is wrong" :-) (i.e. the code does exactly what it's supposed to do, but assuming that a pseudo-prime test is equivalent to a strong primality test is mathematically wrong.) \$\endgroup\$
    – Arnauld
    Jan 15, 2021 at 9:55
1
\$\begingroup\$

JavaScript (Node.js), Cracked by EasyasPi

function max(a, b) {
  if (typeof a !== 'number' || typeof b !== 'number') {
    throw TypeError("This function only accept numbers");
  }
  if (a === b) {
    return a;
  } else if (a > b) {
    return a;
  } else if (a < b) {
    return b;
  } else {
    return Math.max(a, b);
  }
}

function max_ref(a, b) {
  if (typeof a !== 'number' || typeof b !== 'number') {
    throw TypeError("This function only accept numbers");
  }
  return Math.max(a, b);
}

const [a, b] = require('fs').readFileSync(0).toString().split('\n').map(Number);
console.log(max(a, b));
console.log(max_ref(a, b));

Try it online!

For a certain inputs: The program exit normally (without exceptions), and the two lines outputted by above program are different.

I know this could be very simple. But I just cannot get a more complex one under this question...

\$\endgroup\$
1
  • \$\begingroup\$ Cracked \$\endgroup\$
    – EasyasPi
    Jan 16, 2021 at 15:40
1
\$\begingroup\$

Lua (LuaJit)

Find a number bigger than 0.2 where Expected result == Value. Actually the math is right on paper 😜

function Fails(i)
    local max = i * 80
    local a = 0

    while true do
        if a < max then
            a = a + 0.2
        else
            break
        end
    end

    print("Input", i)
    print("Max", max)
    print("Expected Value", max)
    print("Value", a)
end

Fails(...)

Try it Lua

\$\endgroup\$
1
  • \$\begingroup\$ Cracked \$\endgroup\$
    – Dingus
    Jan 17, 2021 at 15:15
0
\$\begingroup\$

Python 3.10.11

import math
def fails(x: float, y: float) -> int:
    return math.lcm(x.as_integer_ratio()[1], y.as_integer_ratio()[1])
  • Takes two real numbers and outputs the lowest natural number that can be the denominator of the fractions representing both numbers (with an integer numerator). For example, \$f(0.1,0.32)=50\$.
  • Incorrect very often, and deterministically.
  • Off by at least a billion times when it's wrong.
  • Infinitely many inputs affected.
  • Version 3.10.11 (maybe other versions), should happen on most environments.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.