4 ms·

> Optional requires generic types (kind-1 types) to be usable My gut tells me that's not quite right (for some reasonable definition of 'usable'), since we can

> Optional requires generic types (kind-1 types) to be usable My gut tells me that's not quite right (for some reasonable definition of 'usable'), since we can always build elimination forms into the language (after all, 'null' must be built in, and few take objection to building in elimination forms like if/then/else). > it also requires some kind of pattern matching or monad comprehensions - otherwise, code using Optional is neither type safe nor readable. I really like comprehensions in Python, but hardly ever use them elsewhere. In fact, when I do use them in Haskell and Scala, I usually find myself having to refactor them into calls to `map`/`join`/etc. soon after, to have more fine-grained scoping or somesuch. > trying to offer a generic SQL library that presents an AST as the API for even the most popular RDBMSs quickly gets complex That's orthogonal to anything I said. Represent SQL using arrays of bytes in memory if you like; offer a string-like interface for constructing and manipulating them if you like; just make sure to distinguish them from other string-like types, in a way that's statically enforceable, and where the only API to convert a 'String' to an 'SQL' is the escaping function. Note that I don't particularly care if an SQL value is valid; it would be nice to statically enforce that, but you're right that (vendor-supplied) SQL is pretty complex in its own right. What's much more important to get right is that SQL is not user-generated.

simiones 5y ago
> My gut tells me that's not quite right (for some reasonable definition of 'usable'), since we can always build elimination forms into the language (after all, 'null' must be built in, and few take objection to building in elimination forms like if/then/else). True, you could go the Go array route and have Optional be a special type that is generic, without otherwise supporting generic data structures. > I really like comprehensions in Python, but hardly ever use them elsewhere. I think code like possiblyMissing.map(value => code) introduces lots of unpleasant imbrication, and breaking out functions for every possibly-missing value also seems to me to lead to bad readability. I suppose this may be a matter of taste, or it may be related to other language features. > just make sure to distinguish them from other string-like types, in a way that's statically enforceable, and where the only API to convert a 'String' to an 'SQL' is the escaping function. I think this is the part that doesn't really work, because, in order to escape a piece of user input, you need to understand what it's meant to be. For example, a common (unsafe) idiom is: sqlFormatString = "SELECT %s FROM %s WHERE %s;"; filterFormatString = "%s LIKE ?"; filterString = sprintf(filterFormatString, userInputColumnName); sqlQuery = sprintf(sqlFormatString, columnName, tableName, filterString); preparedQuery = dbImpl.prepare(sqlQuery, userInputValue); Which of course does the right thing for userInputValue; may or may not be doing the right thing with columnName and tableName, depending on the source; and does the really wrong thing with userInputColumn. Now, you could replace this with a type safe dbImpl.prepare(), which only takes a NotUserGeneratedSQL type. But now you need to have some way to build a NotUserGeneratedSQL. One option is to go all in on an SQL AST library, where you could build the query above like query = selectQuery(); query.columnNames = [ escapeColName(columnName) ]; query.from = escapeTableName(tableName); queryFilter = equalityComparison(); queryFilter.left = escapeColName(userInputColumn); queryFilter.right = preparedArg(); query.filter = queryFilter; preparedQuery = dbImpl.prepare(query, userInputValue) But this, as I said, gets tedious for the user and complex for the implementer. However, I don't think there is any alternative that can actually enforce validation of user input in constructed queries. You can help users think about it by forcing them to use some kind of string -> NotUserGeneratedSQL function, but this function can't actually be written to reject the example I gave initially. A function that creates an empty minimal NotUserGeneratedSQL and offers other functions to build it up to a useful query will either accept strings (making it possible to introduce SQL injection) or have to accept structured SQL, making it fall into the AST problem. Of course, the problem of NotUserGeneratedSQL is easy if you don't want to support any kind of dynamic query, other than prepared statements. But if you want to dynamically generate queries based on user input (e.g. user chooses which columns they want to see, which columns they want to filter by etc.), then I don't think it's possible to statically ensure that SQL injection is not possible without an ORM or SQL AST API. Edit: if you believe otherwise, please show me a type-safe, SQL-injection-safe library in any language that isn't an ORM/EDSL or a straight up SQL AST manipulator. I am quite certain none exists, but I would be happy to be proven wrong.
- chriswarbo 5y ago
  What I had in mind was something along these lines: allowedColumns: Map[UserInput, SQL] = { "name": "name", "age": "age", ... } strict: SQL = strictComparison? "=" : "LIKE" query: Maybe[SQL] = allowedColumns .get(userCol) .map(col => "SELECT " + col + " FROM tbl WHERE tbl.foo " + strict + addParameter(":?", userFoo)) In particular: - We can write literals which look like strings but have type SQL - We can append fragments of SQL together (potentially making it invalid; oh well) - We can include user input via parameterised queries, in locations where arbitrary strings/ints/etc. are allowed - Anything 'structural', like identifiers, choice of comparison operations, building up sub-expressions, etc. must be done programatically, using the above features. In this case we select the column name (written as a static, literal SQL value) by looking up the user's input in a map. We also allow choosing between the type of comparison to use (again, both are SQL literals). It seems to me that requirements like 'user chooses which columns they want to see, which columns they want to filter by etc.' is fundamentally incompatible with a safe, string-like representation. Instead, the options are: - Fully representing the structure of the language. This results in an AST approach, which allows safe dynamic queries. I think any alternative, like tracking the offset of each delimiter in a string, etc. will turn out to be equivalent to maintaining an AST. - A "flat", string-like representation, whose dynamism is limited to choosing between some combination of pre-supplied fragments. This is what I've shown above. This is safe, but the 'dynamism' is inherently limited up-front (i.e. it's overly conservative). - A "flat", string-like representation, which has unrestricted dynamism, but hence is also inherently unsafe (i.e. it's overly liberal).
  - simiones 5y ago
    > - We can write literals which look like strings but have type SQL What I'm not clear is: what prevents me from accidentally/stupidly doing: filter : SQL = "WHERE " + userInputCol + " = ?" Is this special string handling some compiler magic that distinguishes literal strings from string variables? If so then I think that in a language that supports something like this you can indeed make a safe library. The main downside is that you need to work entirely with compile-time constructs - e.g. you can't use something like printf to take a compile-time format string and turn it runtime into a query; and you can't take queries from a separate file, they must be in source code. But these may be acceptable trade-offs. Do you know of any library that implements this?

simiones 5y ago

> My gut tells me that's not quite right (for some reasonable definition of 'usable'), since we can always build elimination forms into the language (after all, 'null' must be built in, and few take objection to building in elimination forms like if/then/else). True, you could go the Go array route and have Optional be a special type that is generic, without otherwise supporting generic data structures. > I really like comprehensions in Python, but hardly ever use them elsewhere. I think code like possiblyMissing.map(value => code) introduces lots of unpleasant imbrication, and breaking out functions for every possibly-missing value also seems to me to lead to bad readability. I suppose this may be a matter of taste, or it may be related to other language features. > just make sure to distinguish them from other string-like types, in a way that's statically enforceable, and where the only API to convert a 'String' to an 'SQL' is the escaping function. I think this is the part that doesn't really work, because, in order to escape a piece of user input, you need to understand what it's meant to be. For example, a common (unsafe) idiom is: sqlFormatString = "SELECT %s FROM %s WHERE %s;"; filterFormatString = "%s LIKE ?"; filterString = sprintf(filterFormatString, userInputColumnName); sqlQuery = sprintf(sqlFormatString, columnName, tableName, filterString); preparedQuery = dbImpl.prepare(sqlQuery, userInputValue); Which of course does the right thing for userInputValue; may or may not be doing the right thing with columnName and tableName, depending on the source; and does the really wrong thing with userInputColumn. Now, you could replace this with a type safe dbImpl.prepare(), which only takes a NotUserGeneratedSQL type. But now you need to have some way to build a NotUserGeneratedSQL. One option is to go all in on an SQL AST library, where you could build the query above like query = selectQuery(); query.columnNames = [ escapeColName(columnName) ]; query.from = escapeTableName(tableName); queryFilter = equalityComparison(); queryFilter.left = escapeColName(userInputColumn); queryFilter.right = preparedArg(); query.filter = queryFilter; preparedQuery = dbImpl.prepare(query, userInputValue) But this, as I said, gets tedious for the user and complex for the implementer. However, I don't think there is any alternative that can actually enforce validation of user input in constructed queries. You can help users think about it by forcing them to use some kind of string -> NotUserGeneratedSQL function, but this function can't actually be written to reject the example I gave initially. A function that creates an empty minimal NotUserGeneratedSQL and offers other functions to build it up to a useful query will either accept strings (making it possible to introduce SQL injection) or have to accept structured SQL, making it fall into the AST problem. Of course, the problem of NotUserGeneratedSQL is easy if you don't want to support any kind of dynamic query, other than prepared statements. But if you want to dynamically generate queries based on user input (e.g. user chooses which columns they want to see, which columns they want to filter by etc.), then I don't think it's possible to statically ensure that SQL injection is not possible without an ORM or SQL AST API. Edit: if you believe otherwise, please show me a type-safe, SQL-injection-safe library in any language that isn't an ORM/EDSL or a straight up SQL AST manipulator. I am quite certain none exists, but I would be happy to be proven wrong.

chriswarbo 5y ago
What I had in mind was something along these lines: allowedColumns: Map[UserInput, SQL] = { "name": "name", "age": "age", ... } strict: SQL = strictComparison? "=" : "LIKE" query: Maybe[SQL] = allowedColumns .get(userCol) .map(col => "SELECT " + col + " FROM tbl WHERE tbl.foo " + strict + addParameter(":?", userFoo)) In particular: - We can write literals which look like strings but have type SQL - We can append fragments of SQL together (potentially making it invalid; oh well) - We can include user input via parameterised queries, in locations where arbitrary strings/ints/etc. are allowed - Anything 'structural', like identifiers, choice of comparison operations, building up sub-expressions, etc. must be done programatically, using the above features. In this case we select the column name (written as a static, literal SQL value) by looking up the user's input in a map. We also allow choosing between the type of comparison to use (again, both are SQL literals). It seems to me that requirements like 'user chooses which columns they want to see, which columns they want to filter by etc.' is fundamentally incompatible with a safe, string-like representation. Instead, the options are: - Fully representing the structure of the language. This results in an AST approach, which allows safe dynamic queries. I think any alternative, like tracking the offset of each delimiter in a string, etc. will turn out to be equivalent to maintaining an AST. - A "flat", string-like representation, whose dynamism is limited to choosing between some combination of pre-supplied fragments. This is what I've shown above. This is safe, but the 'dynamism' is inherently limited up-front (i.e. it's overly conservative). - A "flat", string-like representation, which has unrestricted dynamism, but hence is also inherently unsafe (i.e. it's overly liberal).
- simiones 5y ago
  > - We can write literals which look like strings but have type SQL What I'm not clear is: what prevents me from accidentally/stupidly doing: filter : SQL = "WHERE " + userInputCol + " = ?" Is this special string handling some compiler magic that distinguishes literal strings from string variables? If so then I think that in a language that supports something like this you can indeed make a safe library. The main downside is that you need to work entirely with compile-time constructs - e.g. you can't use something like printf to take a compile-time format string and turn it runtime into a query; and you can't take queries from a separate file, they must be in source code. But these may be acceptable trade-offs. Do you know of any library that implements this?