Mar 29, 2012

CodeIgniter: PHP web app authentication

I have recently begun using CodeIgniter as my PHP framework for quickly whipping up web applications. And as a continuation on my web application blog posts (such as my AJAX with JQuery and PHP tricks) I have decided to whip this one up about how to use the CodeIgniter framework to create a site wide authentication system.

This tutorial assumes some knowledge in database administration and basic knowledge of CodeIgniter (time of writing I was using version 2.1.0) and PHP (version 5.3.10).

Model

First we will need to know the data we will be saving. The following SQL script was created using MySQL, but you should be able to configure with some minor modifications:

CREATE TABLE IF NOT EXISTS `users` (
  `userID` int(10) unsigned zerofill NOT NULL AUTO_INCREMENT COMMENT 'The unique ID',
  `username` varchar(64) NOT NULL COMMENT 'A unique username',
  `password` varchar(128) NOT NULL COMMENT 'The password with embedded salt',
  `personID` int(10) unsigned zerofill NOT NULL COMMENT 'Foreign key to person data',
  `active` tinyint(1) NOT NULL COMMENT 'Whether the user is activated',
  `creationDate` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT 'The date the user was created',
  PRIMARY KEY (`userID`),
  UNIQUE KEY `username` (`username`),
  KEY `personID` (`personID`)
) ENGINE=InnoDB  DEFAULT CHARSET=latin1 AUTO_INCREMENT=1 ;



Now that we know what data we are storing, we can create our model in CodeIgniter. In the folder 'application/models/', create a file called auth_model.php.

<?php if ( ! defined('BASEPATH')) exit('No direct script access allowed');
/**
 * Login Authentication Model Class
 *
 * This is the model that will access authentication data (and provide some
 * functions).
 *
 * @package        Application
 * @subpackage    Models
 * @category    Models
 * @author         Almighty Olive
 * @copyright    Copyright (c) 2012, olivecodex.blogspot.com.au
 */

class Auth_model extends CI_Model
{
    /**
     * Modified constructor class
     */
    function __construct()
        {
            parent::__construct();
       
        // Ensure that sessions are loaded
        $this->load->library('session');
    }

    /**
     * Secure hash generation function.
     *     $input - the data to be hashed
     *     $salt - OPTIONAL: the salt to be used in the hashing function
     *
     * For more info about hashing, please see http://crackstation.net/hashing-security.html
     */
    function createHash($input, $salt = null)
    {
        // If no salt is passed then generate it
        if ($salt === null)   
        {
            //get 256 random bits in hex
            $salt = bin2hex(mcrypt_create_iv(32, MCRYPT_DEV_URANDOM));
        }

        //Prepend the salt, then hash
        $hash = hash("sha256", $salt . $input);
   
        //store the salt and hash in the same string, so only 1 DB column is needed
        $final = $salt . $hash;
   
        return $final;
    }


    /**
     * De-hash function (provided it has been hashed like above)
     * Returns true if the hashed input matches what is stored in the database
     *
     *     $salthash - the salt and hash created by authed_hash (stored in your DB)
     *     $input    - the data to verify
     *     returns   - true if the password is valid, false otherwise.
     *
     * For more info about hashing, please see http://crackstation.net/hashing-security.html
     */
    function validate($input, $salthash)
    {
        // Extract the salt and hash from the stored string
        $salt = substr($salthash, 0, 64); //get the salt from the front of the hash
        $validHash = substr($salthash, 64, 64); //the SHA256

        // Create a hash using the input and salt
        $testHash = hash("sha256", $salt . $input); //hash the password being tested
   
        //If the hashes are exactly the same, the password is valid
        return $testHash === $validHash;
    }
   
    /**
     * For a given username and password combination, this function
     * will look-up the database and determine if the user can access
     * the system
     *     $username = the passed username
     *    $password = the passed password
     *    returns true if the user is active
     */
    function checkAuth($username,$password)
    {
        // Sets up the query parameters
        $this->db->select("*");
        $this->db->where("username",$username);
        $this->db->where("active",'1');

        // Executes the specified query
        $query = $this->db->get("users");

        // Checks that only one row exists
        if(($query->num_rows()>0) && ($query->num_rows()<2))
        {
            $data = array();

            // Grab the resulting row
                $data = $query->row();

            // Checks to see if the password is correct
            if ( $this->validate($password, $data->password))
            {
                    // Create a data array to save to the session session
                    $sessionArray = array( 'userID'=>$data->userID,
                        'username'=>$data->username,
                        'personID'=>$data->personID,
                        'main'=>array(),
                        'logged_in'=>'TRUE');
                    $this->session->set_userdata($sessionArray);

                    // Return from the function
                    return TRUE;
            }
        }

        // If we have arrived here, it means we were not successful
        return FALSE;
    }

    /**
     * Check if a session has already been created
     *    returns true if a session exists
     */
    public function check_session()
    {
        if ($this->session->userdata('userID') AND $this->session->userdata('logged_in')=='TRUE')
        {
            return TRUE;
        } else {
            return FALSE;
        }
    }

    /**
     * Deletes all session data
     *    returns true if a session exists
     */
    public function logout()
    {
        $this->session->unset_userdata('userID');
        $this->session->unset_userdata('logged_in');
        session_destroy();
    }
}
?>


Custom Controller Class

CodeIgniter uses the MVC design pattern, so most of our processing will be through our Controllers. To make our application automatically check if a user has logged in (and redirect them to the login screen if they haven't), we will create a new parent controller class. ALL pages that need authentication will be required to be a child of our new class!

Create a new file in 'application/core/' called 'MY_Controller.php' (change MY_ to whatever you have set it in your config file).

<?php  if ( ! defined('BASEPATH')) exit('No direct script access allowed');

/**
 * Application Controller Class
 *
 * This class object is a super class
 *
 * @package        CodeIgniter
 * @subpackage    Libraries
 * @category    Libraries
 * @author        ExpressionEngine Dev Team
 * @link        http://codeigniter.com/user_guide/general/controllers.html
 */

class MY_Controller extends CI_Controller
{
    function __construct()
    {
    // Performs all the initilisation for a controller
        parent::__construct();

    // Ensure that sessions are loaded
    $this->load->helper('url');

    // Ensure that sessions are loaded
    $this->load->library('session');

    // Load our Authentication Model
    $this->load->model('Auth_model');

    // Check our session to see if we are logged in or not
    if(!$this->Auth_model->check_session()){
        redirect('/auth/login');
    }
    }
}

// END Controller class

/* End of file MY_Controller.php */
/* Location: ./application/core/MY_Controller.php */


Login page controller

Now we need to create a login controller. Note that this controller is NOT derived from our custom class! The custom class redirects to our Login page, so if you do this then you will just end up with a continuous loop!

Create a new file under 'application/controllers/auth/' (create the folder if necessary) called 'login.php'. Note that I am using three view files; header.php, footer.php and login.php. I won't bother making these files as they should be pretty straightforward; you just need a simple form (that redirects to the login page) with a username field, a password field and a submit button.

<?php if ( ! defined('BASEPATH')) exit('No direct script access allowed');

class Login extends CI_Controller {

    /**
     * Constructor for this controller.
     *
     * Load up some common modules
     *
     * @see http://codeigniter.com/user_guide/general/urls.html
     */
    function __construct()
        {
        // Performs all the initilisation for a controller
            parent::__construct();

        // Loads the URL helper (redirection)
        $this->load->helper('url');

        // Ensure that sessions are loaded
        $this->load->library('session');

        // Load our Authentication Model
        $this->load->model('Auth_model');
        }

    /**
     * Index Page for this controller.
     *
     * Maps to the following URL
     *         http://example.com/auth/login
     *    - or - 
     *         http://example.com/auth/login/index
     *
     * @see http://codeigniter.com/user_guide/general/urls.html
     */
    public function index()
    {
        // Loads the form helper
        $this->load->helper('form');

        // Loads the form validation library
        $this->load->library('form_validation');

        // Check our session to see if we are logged in
        if($this->Auth_model->check_session())
        {
            redirect('/');
        }

        // Set the validation rules for the form
        $this->form_validation->set_rules('username', 'Username', 'trim|required|min_length[3]|xss_clean');
        $this->form_validation->set_rules('password', 'Password', 'required');

        // Run Validation check
        if($this->form_validation->run() == TRUE){
            // Grab our submitted data
            $username = $this->input->post('username');
            $password = $this->input->post('password');

            // Check if the user details matches that in our database
            if( $this->Auth_model->checkAuth($username,$password))
            {
                // Authentication is successful
                redirect('/');
            }
        }

        // If we are here it means authentication has failed... load up the error page
        $this->load->view('slair_header');
        $this->load->view('slair_login');
        $this->load->view('slair_footer');
    }

    /**
     * Logout Page for this controller.
     *
     * Maps to the following URL
     *         http://example.com/auth/login/logout
     *
     * @see http://codeigniter.com/user_guide/general/urls.html
     */
    public function logout()
    {   
        // Perform the logout functions
        $this->Auth_model->logout();

        //Goes back to the login screen
        redirect('/auth/login/');
    }
}

/* End of file slair.php */
/* Location: ./application/controllers/slair.php */


Conclusion

You should now be able to just do the following on any controller that requires authentication to access:

class CLASSNAME extends MY_Controller {

     ....

}


The MY_Controller will automatically redirect to the Login page if no session has been detected, otherwise we have a valid user so it will continue processing the rest of the PHP script.

Enjoy!

References:

  • Blog post from Afruj Jahan about writing a simple Login authentication system in CodeIgniter
  • CodeIgniter website
  • List of useful CodeIgniter Tutorials
  • Article about why we should ALWAYS salt our passwords
  • Article about the best way to secure your passwords from Cracked Station

Mar 10, 2012

Using GIT

GIT is a distributed version control system. Unlike SVN, which is centralised, each copy of a git project tree contains it's very own repository. This makes it easier to create branches and forks for development without polluting the main code trunk.

  • To start your first local git repository:
    1. Initialise the repository
      git init
    2. Add all the files in the current directory
      git add .
    3. Commit your initial import
      git commit
  • To monitor changes and logs in your code:
      1. View the revision history
        git log
      2. View the file changes in the repository
        git diff
      3. View the changes for a specific revision and file/directory path
        git diff revision path
      4. Summary of the current changes to the repository
        git status
  •  Some house cleaning functions:
      1. To add a file:
        git add file
      2. To remove a file:
        git rm file
      3. To move a file:
        git mv file
      4. To remove all untracked files (such as temporary files used during compilation):
        git clean
  •  Configure your git instance
      1. Change your username
        git config --global user.name "Your Name"
      2. Change your email
        git config --global user.email email@domain.com
  •  Common functions
      1. Clone an existing repository
        git clone url
      2. Fetch the changes from remote master repository
        git fetch
      3. Similar to above, but this command will merge the changes as well
        git pull
      4. Push your changes to a remote repository
        git push url
      5. Commit all your changes to the local repository
        git commit -a
      6. Edit your last commit with latest changes
        git commit --append
      7. Toss away your last commit
        git reset HEAD^
      8. Assign blame for problematic files
        git blame file
  • Tags and branches
      1. Tags a version
        git tag -a name
      2. List tags
        git tag -l
      3. Show the details about a tag
        git show tag
      4. Create a new branch
        git branch branch
      5. Switch to a branch
        git checkout branch
      6. Delete a branch
        git branch -d branch
      7. List all branches
        git branch
      8. Merges a branch to our current working branch
        git merge branch
 References
http://schacon.github.com/git/gittutorial.html
http://gitref.org 

Mar 9, 2012

AJAX with JQuery and PHP

AJAX stands for Asynchronous JavaScript And XML, and allows us to make our websites seem more dynamic.

A first example...

Our first example outlines how this is done within a single page:

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html>
    <head>
       <meta http-equiv="Content-type" content="text/html; charset=utf-8" />
       <title>Ajax With Jquery</title>

       <!-- Grab the JQuery API from the Google servers -->
       <script src="http://ajax.googleapis.com/ajax/libs/jquery/1/jquery.min.js" type="text/javascript" charset="utf-8"></script>

       <!-- Our own JQuery code to do the AJAX-y stuff -->
       <script type="text/javascript" charset="utf-8">

          $(document).ready(function(){
             $('#txtValue').keyup(function(){
                 $('#display').html($(this).val());
             });
          });

       </script>
    </head>

    <body>
       <label for="txtValue">Enter a value : </label>
       <input type="text" name="txtValue" value="" id="txtValue">

        <div id="display"></div>
    </body>
</html>



Pretty much all this will do is update the display section of of the page with the latest text in the text box. The event the script will listen for is a 'Key Up' event on the txtValue item. Pretty simple really...

Something a little more AJAX - The HTML

So our original example just showed how we could manipulate the DOM (Document Object Model) of the browser during run-time, without a page refresh. How can we use this knowledge utilizing the power of PHP? Well, first let us edit our HTML to something we can manipulate:

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
    <head>
       <meta http-equiv="Content-type" content="text/html; charset=utf-8" />

       <title>Ajax With Jquery</title> <!-- Grab the JQuery API from the Google servers -->
       <script src="http://ajax.googleapis.com/ajax/libs/jquery/1/jquery.min.js" type="text/javascript" charset="utf-8"></script>

       <!-- Our external JS script file... we will write this up later -->
       <script src="tutorial.js"></script>
    </head>

    <body>
         <form name="contact" method="post" action="">
            <label for="txtValue">Enter a value : </label>
            <input type="text" name="txtValue" value="" id="txtValue">
            <input type="button" name="submit" class="button" id="submit_btn" value="Send" />
         </form>
         <div id="display">
         </div>
   </body>
</html>

The JavaScript and JQuery file

Now we need to create the JavaScript file:

$(function() {
    // This will run when the item of class 'button' is clicked
    $(".button").click(function() {
 
         // Grabs the text input
         var name = $("input#txtValue").val();
         var dataString = 'txtValue='+ name;
         // This creates the AJAX connection
         $.ajax({
            type: "POST",
            url: "tutorial.php",
            data: dataString,
            dataType: 'json',
            success: function(data) {
               $('#display').html(data.text);
            }
         });
         return false;
    });
});

This simply sends data to an external php script (tutorial.php) and then change the contents of <div id="display"> to whatever it returns. This is much more AJAX-y.

The PHP file

The final thing we have to do is write the PHP output...

<?php
if (isset($_POST['txtValue'])) {
    $txtValue = stripslashes(strip_tags($_POST['txtValue']));
} else {$txtValue = 'Nothing';}
    echo json_encode(array('text' => $txtValue));
?>


Of course, there are multiple ways of achieving the same result, but this should help you get started.

Reference

Mar 8, 2012

SSH and Keys

Key Generation

On the server run the following command to create a pair of keys in ~/.ssh/ (or whatever the default is configured to on your system):

ssh-keygen
Disclaimer: You may need to install the cryptography packages and openSSH on your system.

The command will create the following files:

  • id_rsa: Your private key. This will identify the user on this machine.
  • id_rsa.pub: The public counterpart of the private key. This is distributed to other users.

On the client machine, copy/append the contents of id_rsa.pub from the server to ~/.ssh/authorized_keys (or whatever it is configured to on your system)
The user on the server should not be able to remotely log into the client without the use of password (as long as the connection is secure)

Example commands

The following example shows how to copy a file from the local machine to a remote machine. The command should not ask for a password if the above steps have been followed correctly and the SSH server is set-up to accept key authentication:

ssh [user@][host] cat < [local_file] ">" [remote_location]

The following example does the opposite: it copies a remote file to a local location:

ssh [user@][host] cat [remote_file] > [local_location]

Mar 7, 2012

PHP Tips and Tricks

Debugging and displaying errors

PHP allows you to edit some configuration options during run-time, including the interpreter error messages. To turn on (or off) these messages you just place the following code:

<?php
error_reporting(E_ALL);
ini_set('display_errors','On');
?>

PHP Sessions

Session code allows us to maintain state information for a user during site navigation and page refreshes. This is immensely useful for account management and shopping cart systems. Using sessions is very, very simple...

<?php
// start up your PHP session! Nothing else is needed...
// All the client-server verification is done in the background
session_start();

// Test to see if a SESSION variable is set or not...
if(isset($_SESSION['views'])) {
     // Variable exists; we can use it
     $_SESSION['views'] = $_SESSION['views']+ 1;
} else {
     // Variable does not exist; create it     $_SESSION['views'] = 1;
}

// Print out a session variable
echo "views = ". $_SESSION['views'];

// Clear a session variable (means it will no longer exist for this user)
if(isset($_SESSION['views'])) {
     unset($_SESSION['views']);
}

// Destroy ALL Session data!!! Make sure you use this wisely!!
session_destroy();
?>

User Details

The following code grabs some details from the user's client browser such as IP Address and HTTPS status:

<?php
// The IP address of the client
$ip=$_SERVER['REMOTE_ADDR']; // The protocol that the information was requested in
$proto=$_SERVER['SERVER_PROTOCOL'];

// The user's browser
$browser=$_SERVER['HTTP_USER_AGENT'];

// Another way to check for HTTPS
$https=$_SERVER['HTTPS'];
?>

MySQL integration

The following code assumes that you have correctly set-up your MySQL database:

<?
// The connection data
$user="username";
$password="password";
$database="database";

// Connect to the database
mysql_connect(localhost,$user,$password);

// Selects a database OR gracefully fails
@mysql_select_db($database) or die( "Unable to select database");

// Creates a SQL that creates a new contacts table (provided that your MySQL user has these permissions
$query="CREATE TABLE contacts (id int(6) NOT NULL auto_increment,first varchar(15) NOT NULL,PRIMARY KEY (id),UNIQUE id (id),KEY id_2 (id))";

// Executes the query on the database
mysql_query($query);

// Closes the database connection
mysql_close();
?>
I am mentioning this seperately because it is pretty much the most important part. SQL Injection is very serious and could compromise your web application; safe-guard against this my escaping your query strings before executing them:
<?php
// An example of a possible input with SQL injection code
$name_evil = "'; DELETE FROM customers WHERE 1 or username = '";

// Use in-built function to escape the bad code
$name_evil = mysql_real_escape_string($name_evil);

// Create a query with the now safe input
$query_evil = "SELECT * FROM customers WHERE username = '$name_evil'";

// Execute this input
mysql_quesry($query_evil);
?>

References

Mar 6, 2012

AI class notes

Some notes I made for an AI class I took a while back:
  • An AI program is called an intelligent agent.
  • An agent interacts with an environment. This environment can be physical or virtual.
  • The agent will perceive the state of this environment, apply internal logic and implement actions upon the environment to change it's state. The feedback loop created can be termed the Perception-action cycle.
  1. Perceive environment through sensors
  2. Apply control logic to determine next best possible move
  3. Implement action through actuators
  4. Repeat from step 1
  • AI has been used in the financial industry (make trading decisions quickly), robotics (to help control cameras, motors, grippers, microphones, touch pads, and speakers), games (to make adversaries seem 'real'), medicine (provide a diagnosis of patients), and on the Internet (search engines).
  • Fully observable: What your agent can sense is enough to deduce the exact state of the environment for decision-making purposes.
  • Partially observable: Aspects of the environment is hidden so the agent needs to make estimates and deduce the probable state of the environment.
  • An example of a partially observable environment is poker. The hands of your opponent and the cards in the deck are kept hidden from the agent; the agent will then need to remember what cards have been played e.t.c to build up an estimate of the probable state to base its move on.
  • Deterministic: The actions of the agent uniquely determine the outcome. For instance, in checkers if the agent moves his piece to a square it will always appear in that square; the piece will not randomly appear elsewhere on the board.
  • Stochastic: The outcome will have some randomness or uncertainty involved. For instance, in snakes and ladders the agent will roll the dice to determine its next move; however the number of spaces is left up to the dice roll and chance.
  • Discrete: The range of inputs and outputs are finite and distinct.
  • Continuous: The range of inputs and outputs are infinite.
  • Benign: The objective of the agent does not contradict yours or others.
  • Adversarial: The objective of the agent is to beat you or others.
  • AI is used to manage uncertainty. If the behaviour of a system is predictable, we can just write normal software to respond and act. AI is designed to respond appropriately when the system displays unpredictable behaviour.
  • The reasons for uncertainty in a system can be because of adversaries (can't predict their move), stochastic (randomness in the environment), laziness and ignorance.
  • A good example of AI is machine translation. Rather than hard-coding word pairs (which would inevitably provide incorrect result), machine translation was achieved through machine learning and AI techniques. The basic process is:
    1. Build a translation model of the probability that a given word correlates with another.
    2. Given a word, the AI will go through its model and find a translation based on the probability table
    3. If it is correct, it is given reinforcement to improve the correlation for future translations. If incorrect, it will decrease the correlation.

Navigation and Search algorithms

In this unit we are only concerned with navigational complexity, where the complexity occurs from deciding on the sequence of actions to get us where we want. This is in contrast to complexity due to not fully perceiving our environment.

Some definitions for the route-finding problem:
  • Initial state of the system is what we know of the environment prior to execution of the system.
  • The Action function determines the actions we can achieve from our current state. The input to this function will be a state, and the output a list of possible actions.

    Action(s) -> {a1, a2, a3, .... , an}
     
  • The Result function determines the possible result of performing an action from our current state. The input will be the action and current state, and the output will be a new state.

    Result(s, a) -> s1
     
  • The GoalTest function tells us if this new state is our goal.

    GoalTest(s) -> True | False
     
  • The PathCost function will tell us the true cost of a sequence of state transitions.

    PathCost((s1, a1)->(s2, a2)->(s3, a3)) -> n
     
  • The StepCost will tell us the true cost of a single transition.

    StepCost(s, a, s1) -> n
     
  • The Frontier is the furthest point/s explored. The frontier defines both the explored and the unexplored areas.
     
  • A Breadth-first or shortest-first search will always choose the shortest path length first (not cost!).
     
  • A Tree-search is a dumb algorithm that simply explores all state transitions, even if it has explored a state previously.
function TREE.search (problem p) returns path

frontier = {path(p.initial)}
loop:

if frontier is empty: return fail
s = path.end
if GoalTest(s): return path
for a in p.actions(s):

add[path+a->Results(s,a)] to frontier
  • A Graph-search solves the problem of re-exploring known states.
function GRAPH.search (problem p) returns path

frontier = {path(p.initial)}
explored = {}
loop:

if frontier is empty: return fail
path = remove_choice(frontier)
s = path.end
add s to explored
if GoalTest(s): return path
for a in p.actions(s):

add[path+a->Results(s,a)] to frontier
unless Results(s,a) in frontier + explored

Remember that tree and graph searches do not simply end when we expand the goal node because it may not be the best path to the goal (i.e. while we have found the goal state, it may not be the optimal path)
  • The Uniform cost or cheapest-first search is guaranteed to find the cheapest overall path cost. The only change to our algorithm is that our path_remove() function will now select our next choice based on lowest total cost.
  • The Depth-first algorithm is the opposite to the breadth-first algorithm in that it will select the longest path first. This is not an optimal solution and is not guaranteed to find the goal, however it requires a lot less memory than the other algorithms as you will only really need to store one path.
These types of searches simply expand out from the initial state until it hits the goal. The search is not directed at all. To improve search performance we can add more information, namely the estimated distance from the current state to the goal.

  • The Greedy Best-first search algorithm is a directed search, but if there are obstacles this search will take you along the line that appears to get you closer to the goal but may not be the best solution.
  • The A* algorithm combines the directed aspect of the Greedy-best-first and the shortest path aspect of the uniform cost searches. It does this by selecting the path that gives the minimal value for f.

    f = g + h
    where:
    g(path) = path cost
    h(path) = h(s) = estimated distance to goal

  • Minimising g() ensures the shortest path, while minimising h() ensures we keep focused on the goal.
     
  • A* depends on the heuristics function h() to find the optimal path. To do this we need to keep h() optimistic and to never overestimate the distance to the goal.
     
  • Optimal if
    h(s) < true cost to the goal through that state
    The logic for the above statement is that all paths on the frontier have an estimated cost greater than the found path as we are exploring using the cheapest first algorithm. Since h() is optimistic (the true cost is greater than the estimated cost), the found path must be the optimal path. For the graph search it is slightly more complicated, but the principles are the same.
     
  • A state space diagram can help map out state transitions.
     
  • Heuristics functions can generated from the rules of a problem, generally by relaxing the rules (or removing rules). By doing this it is as if we are adding operators that dictate how we traverse the state space and therefore reduce complexity. By making it easier we never overestimate and hence have a good h().
     
  • We must remember that h() is just an estimate!!!
     
  • Search works when:
    • Fully observable: Must be able to see the state map.
    • Known: Domain is known; the actions are known to the system.
    • Discrete: Finite number of actions to choose from.
    • Deterministic: The result of taking an action is known.
    • Static: Nothing else in the environment can affect the state of that environment.
  • Nodes are data structures that consist of:
    • State: final state of path
    • Action: what took us here
    • Cost: true total cost up to this point
    • Parent: a pointer to the previous node in the path
Our search algorithms would include two linked lists of nodes: a frontier (priority queue/set) and explored (set).

Hopefully this is useful to someone!

Mar 5, 2012

C++: Dynamic linking library code (linux)

This technique is useful for creating a plug-in architecture; create a header with a standard interfaces and functions that third-party developers can then overwrite. Your code will then load the shared library, create pointer references to the standard functions within the library and then execute the third-party code. I will probably write up another post that will display how this works :D

This was created using Code::Blocks; I dunno why, but I find this IDE easier to use than Eclipse or NetBeans for hobby coding.

First, lets create that header file that describes the standard interfaces and functions.

vo.h
// Ensure the programmer doesn't import our declarations twice.
// This also stops name conflicts from occurring early on.
#ifndef VO_H
#define VO_H

// Prevent the c++ compiler from corrupting names
// and creating "unresolved symbols" when linking
#ifdef __cplusplus
extern "C" {
#endif

// Standard initiliaser
int init( void );

#ifdef __cplusplus
}
#endif

#endif
Just to help us visualise what is happening, let's create the implementation of our header. Nothing too complex... all we will do is return the internal state of a global variable (yes this is not good practice, but it's just for show).

vo.cpp

// Import local libraries
#include "voNameGen.h"

// use the std namespace as the default
using namespace std;

bool bInit = false;

int init( void )
{
return bInit;
}
Now we can compile our shared library. Code::Blocks allowed me to create a project with settings to automatically do this for me, but for those using something different this is the command to run (make sure you do so inside the directory that stores the source code!!):

g++ -fPIC -shared vo.cpp -o libVo.so

So now we have our shared library object. Let's have a quick look inside with nm. This tool shows the symbols inside our library, which are used by other programs to 'hook' into our code. After running the command, you will notice our function, init, is at the bottom of the list. This is the 'hook' we are going to use...

nm -d libVo.so

Now let's use our library!!

testrig.c

// Libraries for input and output
#include <stdio.h>
#include <iostream>

// Library for dynamic linking
#include <dlfcn.h>

// Make sure this points to our
// standard header file!!!!
#include "vo.h"

// Use the standard namespace
// Change only if you know what
// you are doing!!
using namespace std;

int main()
{
    // This will hold our reference
    // to our library...
    void *lib_handle;

   // This is our prototype function
   // for init... note the asterixes
   // (Learn about pointers before
   // changing!!!)
   int* (*init)();

   // Hold out error code
   char *error;

   // Using iostream to create output
   cout << "Hello world!" << endl;

   // Opening up our shared library
   lib_handle = dlopen("libVo.so", RTLD_LAZY);

   // If the library failed to open, exit
   if (!lib_handle)
   {
      // This uses stdlib to create output
      fprintf(stderr, "%s\n", dlerror());
      return 1;
   }

   // Point our function to the address of our desired
   // function located in the library....
   init = (int* (*)())dlsym(lib_handle, "init");

   // If we failed to find the function, exit
   if ((error = dlerror()) != NULL)
   {
      // This uses stdlib to create output
      fprintf(stderr, "%s\n", error);
      return 1;
   }

   // Execute the function in the library
   // and pipe the output directly to the
   // command line
   cout << fn() << endl;

   // Close our library and save memory
   dlclose(lib_handle);

   // Exit the program
   return 0;
}
There is nothing more I can really add to this; just go through the code and read the comments! To compile this code manually just type in (the -ldl flag is important as it tells the compiler to use the dlfcn library):

g++ -ldl main.cpp -o main

UPDATE: It has been noticed in the comments that "g++ main.cpp -ldl -o main" works instead of "g++ -ldl main.cpp -o main". Keep this in mind in case you come across any errors.

Now just make sure libVo.so is in the same directory as main before you execute it!

References

A Stack Overflow discussion on the topic
The YoLinux tutorial on the topic of libraries

Mar 2, 2012

ISO image editing

Recently I had to work with extracting and editing an existing Linux installation CD, and then to create my own image. To make it easier for those in my situation (and to make it easier for me to remember), here is my solution!!

Extracting CD for editing

You can directly extract the contents of a CD using the rsync command:

rsync -av /cdrom/ /opt/cd-image
Or, if you are using an ISO image, just mount the .iso and copy the contents directly to your working directory:
mount -o loop /path/to/iso /some/mountpoint
cp -rT /some/mountpoint /opt/cd
Creating boot-able CD from directory

This command will create a CD that is boot-able by most systems. If you don't want to create a boot-CD, you can skip most of the options in between -V and -o options. Anyway, the solution!

#!/bin/bash
#
# CD image name
IMAGE=bootcd.iso
# The build directory (where you extracted the CD earlier)
BUILD=/opt/cd/
#
# Create the bootable CD
mkisofs -r -V "AssetOS" -cache-inodes -J -l -b isolinux/isolinux.bin -c isolinux/boot.cat -no-emul-boot -boot-load-size 4 -boot-info-table -o $IMAGE $BUILD

Some hints to save you going through man pages:
  • -b parameter requires the location of the El Torito boot image. In the above command the location of this image is relative to the $BUILD directory
  • -c parameter requires the location of the boot catalog. Without this catalog the CD will not be bootable
  • -J parameter creates Joliet records in addition to standard ISO9660 filenames. This is useful only if the CD will be used on Windows systems.
  • -l parameter allows for the full length filenames
  • -r sets the permissions of all the files on the CD into values that are useful for future users of the system (i.e. GUID and UID are not set to something unusable on a different system)
  • -cache-inodes determines what the system should do with file links. In this case, the CD will have the same links as on the original filesystem.

Mar 1, 2012

Troubleshooting USB mobile internet in Ubuntu

Most mobile broadband USB sticks come with two partitions; one with the installer and the other with the actual connection device. When you plug in the USB, the operating system will first mount the installer partition (which usually contains the installers for Windows and Mac). The installer will insert code that will automatically switch the USB to skip the installer and mount the connection device directly. Unfortunately most manufacturers don't support Linux, so new USB devices won't work straight away.

This guide will provide some tips to get your troublesome USB broadband stick working. This guide will focus on Ubuntu (11.04 in particular), however most of this guide should be applicable to other distro's as well (as long as it has usb_modeswitch installed). The particular device I will be configuring is the Huawei Technologies K3771 USB device given by Vodafone Australia.

First we will go through some troubleshooting tips for those new to the game, and by step 3 we will begin applying our fix.


  1. Plug-in your device, open up a terminal (or command prompt) and type in the following command:

    nm-tool

    This will open up a list of internet devices; eth stands for ethernet and is usually your wired/wireless connections. We are looking for entries with wwan, GSM, 3G or Mobile Broadband in this list. If your device is detected here but does not work then it is a software issue that is outside the scope of this guide.
     
  2. Now we need to see if your device is even detected by the system. Unplug your device, wait a second and in the terminal type in:

    lsusb > ~/usb1.txt

    When the command finishes plug the device back in, wait ALOT of seconds (wait until LEDs start flashing) and type in:

    lsusb > ~/usb2.txt

    Now to see if anything changed. Type in the command:

    diff ~/usb1.txt ~/usb2.txt

    You should now see something like:

    6a7> Bus 002 Device 008: ID 12d1:14c4 Huawei Technologies Co., Ltd

    If nothing pops up on the terminal, then either you jumped the gun too early with the second lsusb OR your device simply isn't playing nice. This is outside the scope of this guide and I suggest you hit up the guys at libusb or kernel developers to track this problem down. But before you do just cross your fingers and try:

    sudo /usr/sbin/update-usbids

    This will update the id list of USB devices your system will support; hopefully it will be in there!!
     
  3. So now the hard part starts. The line we got from lsusb gives us some useful information about the device. The ID of a device can be split into two parts; the first part (12d1) is the vendor code, and the second part (14c4) is the product code. Unfortunately, in this case the product code points to the installer partition of the device. We need to manually tell the system to switch over to the mobile broadband part (this is what the installer does automatically for Windows and Mac). To do this we run the following command:

    sudo gedit /lib/udev/rules.d/40-usb_modeswitch.rules

    This will bring up a text editor with a list of all the USB devices that the system will automatically switch. We now need to add our device to this list. Either add to the end of the file or do a search to find similar devices and add:

    # This is just a comment. Replace this text with information of your device
    ATTRS{idVendor}=="12d1", ATTRS{idProduct}=="14c4", RUN+="usb_modeswitch '%b/%k'"

    Replace the vendor and product id's with whatever lsusb produced. It should look like:

    # Vodafone (Huawei) K3771
    ATTRS{idVendor}=="12d1", ATTRS{idProduct}=="14c4", RUN+="usb_modeswitch '%b/%k'"

    Ok, so now we are telling the system to switch our device.... switch to what? Remember, no matter how fancy they get computers are always very, very stupid machines. The mobile broadband device has it's own product id that we must link to the installer id. This is where it gets tricky; you need to figure out what this id is and at this stage I have no other advice other than to Google and pray. Luckily for me I know that my device id is 12d1:14ca. Now we need to create a custom usb_modeswitch rule.....
     
  4. Navigate to the directory /usr/share/usb_modeswitch/ by running the following command in a terminal:

    cd /usr/share/usb_modeswitch/

    If you perform an ls you will see that this directory contains a file called configPack.tar.gz. This file contains all the switching rules; we need to edit it to add our device. First back up the file through:

    sudo cp configPack.tar.gz configPack-ORIGINAL.tar.gz

    Now we will extract the scripts through running:

    sudo mkdir configPack/; sudo tar xzf configPack.tar.gz -C configPack/

    Run the command to open a text file for our new rule (replace the 12d1:14c4 part with the id of your device):

    sudo gedit configPack/12d1\:14c4

    This will open a completely blank document. Add the following text (remember to customise for your particular device!):

    ##########################################
    # Vodafone (Huawei) K3771 (again, this is just a comment)
    #
    # Our settings discovered by lsusb (the '0x' part just
    # tells the system how to interpret the number
    DefaultVendor= 0x12d1
    DefaultProduct=0x14c4
    #
    # Our target product that we will switch to
    TargetVendor= 0x12d1
    TargetProduct= 0x14ca
    #
    # Some misc values that I don't really understand and am
    # not game enough to change...
    CheckSuccess=20
    MessageContent="55534243123456780000000000000011062000000100000000000000000000"

    Now we need to repack the rules and clean up our mess:

    cd configPack/; sudo tar -czf ../configPack.tar.gz *; cd ../; sudo rm -rf configPack/

    You can check the contents of the file by running the following command:

    sudo file-roller configPack.tar.gz
     
  5. Now restart your machine and, fingers crossed, the system will now correctly detect your device!

References

Some useful links for those who want to trace something more specific: