headers
Ben Crowell | 1 Dec 2004 01:05
Favicon

Turing-incomplete Lua?

Is there any reasonably easy way to use Lua as a data-
description language, while disallowing the features
that make it a Turing-complete language? For instance,
Unix and the apps that run on it have traditionally had
lots and lots of configuration files, each of which had
its own idiosyncratic syntax. It would be nice to be able
to standardize them in terms of syntax. I believe MacOS X
uses XML for a lot of its config files, for instance.
However, sometimes it's nice to have a real programming
language, and XML isn't a programming language per se.
For instance, it would be nice to be able to use conditional
constructs in a config file: if the operating system is
FreeBSD, then X, else if it's Linux, ... But you probably
don't want a Turing-complete language for this purpose,
for reasons of reliability and trust; it's fundamentally
impossible for a computer program to verify or manipulate
another program written in a Turing-complete language.
This is why I'm much more willing to accept an
e-mail written in HTML (a Turing-incomplete language) than
one that contains an executable program. Another interesting
example is TeX, which is Turing-complete; spell-checkers for
TeX are always full of weird heuristics for attempting to
determine what should be spell-checked and what shouldn't,
and the problem is fundamentally impossible to solve because
of the Turing-complete nature of the language.

So if you can see what I'm getting at --- is there a way
to read a data description written in Lua, but make sure it's
sufficiently limited in what it does that we know it's
limited to a Turing-incomplete subset of Lua? A couple of
(Continue reading)

Permalink | Reply | 22 comments |
headers
Luiz Henrique de Figueiredo | 1 Dec 2004 01:25
Picon

Re: Turing-incomplete Lua?

> Is there any reasonably easy way to use Lua as a data-
> description language, while disallowing the features
> that make it a Turing-complete language?

I'm not sure that's what you mean, but if your data description is a series of
expressions, you may be able to do what you want by simply prepending "return "
to the file before compiling. This will avoid all procedural constructs in
the main chunk.

However, itt won't be completely safe because you still write things like
	return (function () for i=1,10 do print(i) end end)()

To handle these, you could set up a call hook and raise an error at run time.
(You still need to allow the chunk to run, and this is a function call; so
you need to disallow nested functions calls.)
--lhf
Permalink | Reply | 0 comments |
headers
Asko Kauppi | 1 Dec 2004 02:07
Picon

Re: Turing-incomplete Lua?


Imho, this is not a question of Turing-to-or-not but of proper 
sandboxing, right?  I mean, if there's absolutely no way the program 
can contact outside world (read files etc.) then what harm could 
turingness possibly do?

OTOH, ability to read files etc. would be beneficial in the 
configuration files, so.. it's about where you draw the line. Perhaps 
just disallow any writes? Sandboxing per se is relatively easy with 
Lua.

-ak

1.12.2004 kello 02:05, Ben Crowell kirjoitti:

  Is there any reasonably easy way to use Lua as a data-
> description language, while disallowing the features
> that make it a Turing-complete language? For instance,
> Unix and the apps that run on it have traditionally had
> lots and lots of configuration files, each of which had
> its own idiosyncratic syntax. It would be nice to be able
> to standardize them in terms of syntax. I believe MacOS X
> uses XML for a lot of its config files, for instance.
> However, sometimes it's nice to have a real programming
> language, and XML isn't a programming language per se.
> For instance, it would be nice to be able to use conditional
> constructs in a config file: if the operating system is
> FreeBSD, then X, else if it's Linux, ... But you probably
> don't want a Turing-complete language for this purpose,
> for reasons of reliability and trust; it's fundamentally
(Continue reading)

Permalink | Reply | 19 comments |
headers
Milano Carvalho | 1 Dec 2004 02:58
Picon
Favicon

RE: Turing-incomplete Lua?

If I understood you, what you want is to know if there is a way to have a 
"minimized Lua" grammar (Turing-incomplete) that would be possible to say if 
a program written in such "minimized Lua" halt or not. If it would be 
possible we would have a function (without infinite-loop) that receives a 
"minimized Lua" program and return true if it halts or false otherwise.

It is not possible if the "minimized Lua" grammar (whatever language in 
fact) keep the loop statements. It is related to the halting problem a 
mathematical theorem.

Maybe I missed all the point or I forgot something... :-)

Milano

>From: Ben Crowell <luacrowell04 <at> lightandmatter.com>
>Reply-To: Lua list <lua <at> bazar2.conectiva.com.br>
>To: lua <at> bazar2.conectiva.com.br
>Subject: Turing-incomplete Lua?
>Date: Tue, 30 Nov 2004 18:05:18 -0600
>
>Is there any reasonably easy way to use Lua as a data-
>description language, while disallowing the features
>that make it a Turing-complete language? For instance,
>Unix and the apps that run on it have traditionally had
>lots and lots of configuration files, each of which had
>its own idiosyncratic syntax. It would be nice to be able
>to standardize them in terms of syntax. I believe MacOS X
>uses XML for a lot of its config files, for instance.
>However, sometimes it's nice to have a real programming
>language, and XML isn't a programming language per se.
(Continue reading)

Permalink | Reply | 0 comments |
headers
Diego Nehab | 1 Dec 2004 03:37
Picon

Re: LuaSocket and require

Hi,

> Naturally, these two version of require are completely incompatible!
> I'm faced

This has been widely discussed here on the list and we all seem to have
reached an agreement (some of us more than others, it's true) on a
standard for packaging in Lua.

The next release of LuaSocket (which is ready but still needs some
testing) already supports that standard.

Best regards,
Diego.
Permalink | Reply | 0 comments |
headers
Matt Hellige | 1 Dec 2004 05:55

Re: Turing-incomplete Lua?

[Asko Kauppi <asko.kauppi <at> sci.fi>]
> 
> Imho, this is not a question of Turing-to-or-not but of proper 
> sandboxing, right?  I mean, if there's absolutely no way the program 
> can contact outside world (read files etc.) then what harm could 
> turingness possibly do?

Presumably you don't want to allow configuration files to cause
infinite loops... You could probably address that with a simple
timeout in most cases, and use sandboxing for the stuff you mention.

Matt

--

-- 
Matt Hellige                  matt <at> immute.net
Permalink | Reply | 16 comments |
headers
Ben Crowell | 1 Dec 2004 06:14
Favicon

Turing-incomplete Lua?

Asko Kauppi wrote:
>Imho, this is not a question of Turing-to-or-not but of proper
>sandboxing, right?  I mean, if there's absolutely no way the program
>can contact outside world (read files etc.) then what harm could
>turingness possibly do?

>OTOH, ability to read files etc. would be beneficial in the
>configuration files, so.. it's about where you draw the line. Perhaps
>just disallow any writes? Sandboxing per se is relatively easy with
>Lua.

I think there is one whole class of applications where sandboxing
works fine, and another class where the real issue is Turing-completeness.

A good sandboxing example would be the barbie.com web site that my
daughters think is the main reason for the internet's existence.
You go to the site, and it runs a flash application, which lets
you do things like dress Barbie up in different clothes, give her
a makeover, etc. The application does not and should not read or
write files on my computer. It runs in a sandbox, and everyone's
happy.

OTOH, I think configuration files are a perfect example of something
where sandboxing won't work. The whole point of, say, sendmail's
configuration file is that sendmail is going to handle a bunch of
e-mail messages for me, and that means reading and writing files
on disk. The config file itself may not be a program that says
"write this to this mailbox," but the config file's reason for
existing is to control the behavior of a program that will write
something to a particular mailbox.
(Continue reading)

Permalink | Reply | 4 comments |
headers
Jeff Koftinoff | 1 Dec 2004 06:17
Favicon
Gravatar

Re: Turing-incomplete Lua?


On 30-Nov-04, at 8:55 PM, Matt Hellige wrote:

>
> Presumably you don't want to allow configuration files to cause
> infinite loops... You could probably address that with a simple
> timeout in most cases, and use sandboxing for the stuff you mention.
>
> Matt
>

But if you made the mini-lua grammar simple enough you could guarantee 
that there would be no possibility of infinite loops.  A timeout is 
problematic in many ways! Please don't do things like that.

If you just restrict the grammar so that all loops have a fixed repeat 
count (non-variable) and no recursive function definitions are allowed 
then you don't need a sandbox and you don't need problematic 
halt-sensing and you can be guaranteed that the config file will never 
halt your process.  I believe a system like this would be very very 
useful.

Jeff

--
Jeff Koftinoff <jeffk <at> jdkoftinoff.com>
www.jdkoftinoff.com
Permalink | Reply | 5 comments |
headers
Diego Nehab | 1 Dec 2004 06:40
Picon

Re: Turing-incomplete Lua?

Hi,

What is it that you are trying to accomplish? Concretely, what is it that
Lua can do that you don't want your description language to be able to
do?

[]s,
Diego.
Permalink | Reply | 2 comments |
headers
Mike Ferenduros | 1 Dec 2004 06:50
Picon

Re: Turing-incomplete Lua?

You'd also want to prevent malicious scripts from eating all available 
memory.
Incidentally, is this for a particular application? Off the top of my 
head, I can't think of anything that would use an untrusted config file.

Jeff Koftinoff wrote:

>
> On 30-Nov-04, at 8:55 PM, Matt Hellige wrote:
>
>>
>> Presumably you don't want to allow configuration files to cause
>> infinite loops... You could probably address that with a simple
>> timeout in most cases, and use sandboxing for the stuff you mention.
>>
>> Matt
>>
>
> But if you made the mini-lua grammar simple enough you could guarantee 
> that there would be no possibility of infinite loops.  A timeout is 
> problematic in many ways! Please don't do things like that.
>
> If you just restrict the grammar so that all loops have a fixed repeat 
> count (non-variable) and no recursive function definitions are allowed 
> then you don't need a sandbox and you don't need problematic 
> halt-sensing and you can be guaranteed that the config file will never 
> halt your process.  I believe a system like this would be very very 
> useful.
>
> Jeff
(Continue reading)

Permalink | Reply | 1 comment |

Gmane