News for hackers. Stuff that matters.
Re:Crema: A Sub-Turing Programming Language by kazinator on Wednesday August 05, 2015 @01:56PM (#10011548)
You can easily put a cap on computational power without dumbing down the language, via external resource limits: how many CPU cycles can be executed (or abstract processor time), how much memory can be allocated, and how deep the stack can go.

Such parameters are easily administered and easy to understand for IT people.

The limitations in a less-than-Turing language don't nicely translate to a hard cap on the running time. Attackers can find convoluted programs which maximize running time by skirting every available limit.

Re:Crema: A Sub-Turing Programming Language by schoen on Wednesday August 05, 2015 @02:38PM (#10011831)
I don't think this is the right sense of "computational complexity" or of the constraints here. Consider:

  ulimit -t 1; nc -l 55555 | xargs -0 python -c
versus

  python -c 'print len([n for n in xrange(10**15) if str(n) == str(n)[::-1]])'
The second one can (and will) use more CPU time than the first one, guaranteed, but the second one is safer and we can have a very concrete understanding of why.

I think in LANGSEC, the crux of the matter is decidability, not time complexity. And those are ultimately distinct issues, even though both are studied in theoretical computer science.

Re:Crema: A Sub-Turing Programming Language by kazinator on Wednesday August 05, 2015 @07:33PM (#10013630)
The second one is safer because you control the code; you're not executing code read from a network.

I don't believe that this is the topic here (comparing untrusted versus trusted code).

The issue is: if we already have a properly sandboxed language, such that we can expose it as an input language, we can still be DDoS attacked by inputs that perform "too much computation". They take too long, and/or chew memory. Sandboxing has to take these attacks into account also, not only restricting what the code has access to.

(My point was that external resource limits can achieve this without crippling the expressivity of the language.)

> I think in LANGSEC, the crux of the matter is decidability, not time complexity.

I see that.

From langsec.org: "LANGSEC posits that the only path to trustworthy software that takes untrusted inputs is treating all valid or expected inputs as a formal language, and the respective input-handling routines as a recognizer for that language. The recognition must be feasible, and the recognizer must match the language in required computation power."

Okay, so that implies decidability. The LANGSEC approach seems to rule out inputs which are Turing complete computational languages, because recognizing whether they are valid means running them, and is thus equivalent to the Halting Problem.

Time complexity is secondary to the guarantee that recognition terminates (deciding yes, the input conforms or no it doesn't). That's a matter of tuning the permitted input size versus the recognizer algorithm's asymptotic complexity.

However, in some application domains we must have inputs (or do have them, in any case) which are in fact computational languages (e.g. Javascript inputs to a browser). We cannot banish these because some LANGSEC forum wants every input to be recognized syntactically as a piece of formal syntax, not having any semantics as a piece of code which unfold only through execution. Still, such inputs should be treated formally as much as possible rather than in an ad hoc way.

Re:Crema: A Sub-Turing Programming Language by madflame991 on Wednesday August 05, 2015 @03:01PM (#10012027)
Agreed, regular expressions are not turing complete and they can still make your browser ponder for a bit if carefully crafted. Try

  /(x+x+)+y/.test('xxxxxxxxxxxxxxxxxxxxxxxxxxxxx')
for instance. This regex doesn't even use non-regular extensions; it's expressible in a very limited computational model, it fits in a tweet and yet it renders my browser unresponsive.

I can do even more damage with a nasty shader; GLSL is not turing complete either (in fact it looks a lot like Crema).

Re:Crema: A Sub-Turing Programming Language by black_knight on Thursday August 06, 2015 @01:27AM (#10014698)
Well, there are faster implementations of regexp than the one your browser most likely is using [1].

[1] http://swtch.com/~rsc/regexp/regexp1.html

Re:Crema: A Sub-Turing Programming Language by schoen on Wednesday August 05, 2015 @03:40PM (#10012294)
That's a nice example.