Wednesday, January 6, 2010

Chapter 18. Graph Search



[ Team LiB ]






Chapter 18. Graph Search


We often learn properties of a graph by systematically examining each of its vertices and each of its edges. Determining some simple graph properties�for example, computing the degrees of all the vertices�is easy if we just examine each edge (in any order whatever). Many other graph properties are related to paths, so a natural way to learn them is to move from vertex to vertex along the graph's edges. Nearly all the graph-processing algorithms that we consider use this basic abstract model. In this chapter, we consider the fundamental graph-search algorithms that we use to move through graphs, learning their structural properties as we go.


Graph searching in this way is equivalent to exploring a maze. Specifically, passages in the maze correspond to edges in the graph, and points where passages intersect in the maze correspond to vertices in the graph. When a program changes the value of a variable from vertex v to vertex w because of an edge v-w, we view it as equivalent to a person in a maze moving from point v to point w. We begin this chapter by examining a systematic exploration of a maze. By correspondence with this process, we see precisely how the basic graph-search algorithms proceed through every edge and every vertex in a graph.


In particular, the recursive depth-first search (DFS) algorithm corresponds precisely to the particular maze-exploration strategy of Section 18.1. DFS is a classic and versatile algorithm that we use to solve connectivity and numerous other graph-processing problems. The basic algorithm admits two simple implementations: one that is recursive, and another that uses an explicit stack. Replacing the stack with a FIFO queue leads to another classic algorithm, breadth-first search (BFS), which we use to solve another class of graph-processing problems related to shortest paths.


The main topics of this chapter are DFS, BFS, their related algorithms, and their application to graph processing. We briefly considered DFS and BFS in Chapter 5; we treat them from first principles here, in the context of search-based graph-processing classes, and use them to demonstrate relationships among various graph algorithms. In particular, we consider a general approach to searching graphs that encompasses a number of classical graph-processing algorithms, including both DFS and BFS.


As illustrations of the application of these basic graph-searching methods to solve more complicated problems, we consider algorithms for finding connected components, biconnected components, spanning trees, and shortest paths, and for solving numerous other graph-processing problems. These implementations exemplify the approach that we shall use to solve more difficult problems in Chapters 19 through 22.


We conclude the chapter by considering the basic issues involved in the analysis of graph algorithms, in the context of a case study comparing several different algorithms for finding the number of connected components in a graph.






    [ Team LiB ]



    DB2 Trace



    [ Team LiB ]





    DB2 Trace


    The DB2 trace facility has been significantly improved in v8 and it can now be used as one of the primary tools for gathering information regarding a problem. However, the DB2 trace should only be used in conjunction with DB2 Support. DB2 trace records information about operations and formats it into a readable form. On UNIX, sysadm, sysctrl, or sysmaint authority is required. On Windows, no authorization is required.


    NOTE



    db2trc can be used to trace activity for an instance or for the DB2 Administration server.



    A connection to the database is not required. db2trc is useful when other FFDC facilities have failed to provide you and DB2 Support with enough information to identify and solve the problem being investigated. The following is an example of the db2trc command:



    db2trc on �p 20, 40, 60

    The example command causes tracing to be enabled for processes 20, 40, and 60. Use the following command to dump the trace information to a file:



    db2trc dmp dbtrc.dmp

    After you have dumped the trace to a file you must stop the trace as follows:



    db2trc off

    After you have turned the trace off, you can format it using the flw or fmt option.


    Note that the db2trc command has to be issued multiple times to gather the information and format it to a text file. For further information, refer to the DB2 UDB v8 Command Reference.





      [ Team LiB ]



      Recipe 3.5 Creating Rollovers Without JavaScript











       < Day Day Up > 







      Recipe 3.5 Creating Rollovers Without JavaScript







      Problem





      You want to create a simple



      rollover effect without using

      JavaScript to swap images.









      Solution





      Use the :hover and

      :active

      pseudo-classes to create the rollover:





      a:link {

      color: #777;

      text-decoration: none;

      }

      a:visited {

      color: #333;

      text-decoration: none;

      }

      a:link:hover, a:visited:hover {

      color: #777;

      background-color: #ccc;

      }

      a:link:active, a:visited:active {

      color: #ccc;

      background-color: #ccc;

      }











      Discussion





      The :hover pseudo-class mimics the common

      JavaScript event

      onmouseover. Instead of executing a function in

      JavaScript, when a user rolls over a link with

      :hover, a different set of styles is applied to

      the link.





      With the selectors having the same specificity, selectors written out

      of order may stop one of the other styles from appearing. Avoid this

      common problem by listing the selectors in the order:

      link, visited,

      hover, and active. The mnemonic

      device commonly used to remember the order is

      "LoVe/HAte."





      Although :hover and :active can

      be applied to any element, they are commonly used on links. Note that

      browser support for :hover and

      :active is nonexistent in Netscape Navigator 4.

      Also, Opera 4 doesn't support

      :hover.





      In the Solution, the two pseudo-classes make sure that the rollover

      effects occur only on anchor links. Without :hover

      and :active, modern browsers could legally apply

      the rollover effects on any anchor elements, as shown in this code

      and in Figure 3-4:





      <h2><a name="europan">Li Europan lingues</a></h2>









      Figure 3-4. An unwanted rollover effect on a heading











      See Also





      The CSS 2.1 specification for :active and

      :hover at http://www.w3.org/TR/CSS21/selector.html#x36;

      an explanation about links and specificity at http://www.meyerweb.com/eric/css/link-specificity.html.



















         < Day Day Up > 



        References





        References



        More about NetBIOS and SMB/CIFS



        lang=EN-GB style='font-size:10.0pt;font-family:Symbol'>�        
        NetBIOS specifications: style='color:#003399'>http://www.faqs.org/rfc/rfc1001.txt style='color:#003399'>http://www.faqs.org/rfc/rfc1002.txt



        lang=EN-GB style='font-size:10.0pt;font-family:Symbol'>�        
        Online version of using Samba: style='color:#003399'>http://samba.he.net/using_samba/



        Samba



        lang=EN-GB style='font-size:10.0pt;font-family:Symbol'>�        
        Homepage: http://www.samba.org/



        lang=EN-GB style='font-size:10.0pt;font-family:Symbol'>�        
        Download: lang=EN-GB style='color:#003399'>http://www.samba.org/samba/ftp/samba-latest.tar.gz
        lang=EN-GB style='color:#003399'>ftp://ftp.samba.org/pub/samba/samba-latest.tar.gz



        TkSmb



        lang=EN-GB style='font-size:10.0pt;font-family:Symbol'>�        
        Homepage: style='color:#003399'>http://www.rt.mipt.ru/frtk/ivan/TkSmb/



        lang=EN-GB style='font-size:10.0pt;font-family:Symbol'>�        
        Download: http://www.rt.mipt.ru/frtk/ivan/TkSmb/Arc/TkSmb-0.9.0.tar.gz



        xSMBrowser



        lang=EN-GB style='font-size:10.0pt;font-family:Symbol'>�        
        Homepage: lang=EN-GB style='color:#003399'>http://www.public.iastate.edu/~chadspen/



        style='font-size:10.0pt;font-family:Symbol'>�        
        Download: http://www.public.iastate.edu/~chadspen/xsmbrowser-2.4.0.tar.gz



        SMB2WWW



        style='font-size:10.0pt;font-family:Symbol'>�        
        Homepage: http://www.samba.org/samba/smb2www/



        Ghostscript



        style='font-size:10.0pt;font-family:Symbol'>�        
        Homepage: style='color:#003399'>http://www.cs.wisc.edu/~ghost/



        style='font-size:10.0pt;font-family:Symbol'>�        
        Download: style='color:#003399'>http://www.cs.wisc.edu/~ghost/doc/gnu/index.htm



         





        Sound Effects and Filtering





        Sound Effects and
        Filtering



        The next step is to apply effects or filtering to modify the
        sound quality of your recording, if necessary. One situation where filtering
        might be useful is when capturing live audio from a microphone. Depending on
        the quality of the microphone and the acoustics of the recording space, you may
        need to perform frequency filtering or apply minor effects to give the
        recording a fuller sound.



        Volume
        Adjustment



        Despite the precuations you may have taken setting the correct
        recording volume, sometimes an audio clip is just too quiet. If you've obtained
        the clip from somewhere else, you may have no choice in the matter. It's easy
        to use SOX to boost the volume level of the file. In fact, this can be done
        simultaneously with any other operation SOX supports. The first step is to find
        out how much the volume must be boosted:



        $ sox mysong.wav -e stat
        Maximum amplitude: 0.803
        Minimum amplitude: 0.000
        Mean��� amplitude: 0.006
        Maximum delta:���� 0.690
        Minimum delta:���� 0.000
        Mean��� delta:���� 0.003
        Volume adjustment: 1.245


        The command runs some statistics on the samples in the file
        and prints the results. For us, the important one is the Volume adjustment
        suggestion. This indicates that we need to boost the volume about 24%. And we can
        immediately do this:



        $ sox mysong.wav -v 1.245 newsong.wav


        newsong.wav is created, with
        an optimal volume. This technique can also be used to soften the volume of an
        audio clip. Keep in mind, though, that if the recording volume was too high
        when the clip was recorded, lowering the volume of the file will not make the
        crackling go away. It will just be softer, like the rest of the file.



        If graphical applications are your thing, you can use audacity
        to do exactly the same thing. The menu option is under Effect/Amplify. You also
        have the option of boosting the volume of certain sections, instead of applying
        the change to the entire file.



        Frequency
        Filtering: High-Pass, Low-Pass, Band-Pass "Graphic Equalizer"



        Frequency filtering is most familiar in the sense of a graphic
        equalizer. In the earlier section Types of Digital Audio, I discussed how
        frequency encoding converts an audio clip into a set of volumes. Frequency
        filtering is a mathematical operation that changes these volumes relative to
        one another. style='color:#003399'>Figures 19-4 and style='color:#003399'>19-5 show a sample frequency encoding. The
        spikes you see are the pure tones with the highest volumes. Notice how, in style='color:#003399'>Figure 19-5, the lower-pitched frequencies are
        suppressed.



        style='font-size:10.5pt;font-family:Arial'>Figure 19-4. A frequency spectrum
        before filtering.




        style='font-size:10.5pt;font-family:Arial'>Figure 19-5. The same frequency
        spectrum as in style='color:#003399'>Figure 19-4 after applying a high-pass filter.




        Although frequency filtering can be done very
        precisely, the human ear generally recognizes three broad categories: treble,
        midrange, and bass. Too much bass or too little treble leads to a
        "muffled" sound, whereas too much treble or too little bass leads to
        a "tinny" sound. The human voice generally falls in the lower end of
        the midrange frequencies, so vocals can be enhanced by boosting the midrange. Karaoke
        machines work by selectively filtering in the 2- to 4-KHz range while allowing
        other frequencies through.



        Again, SOX excels at performing equalization.
        SOX provides low-pass, band-pass, and high-pass filters, which decrease the
        amount of treble, midrange, and bass, respectively. The filter called class=docemphasis1>tape-deemph
        is also useful when recording directly
        from a television or DVD audio signal. All of these filters can be invoked
        during file format conversion. Consider the following commands:



        $ sox infile.au tape-deemph outfile.wav
        lang=EN-GB>$ sox outfile.wav highp 4000 outfile-hp.wav


        The first command performs a format
        conversion while applying the tape-deemph filter, and the second applies an
        additional high-pass filter centered at 4KHz and saves the recording into a new
        WAV file. SOX is restricted to one filter per invocation, but it supports pipes
        for input and output, so the previous pair of commands could be reduced to the
        following command line:



        $ sox infile.au tape-deemph - | sox - highp 4000 outfile-hp.wav


        A word of caution: Many audio players for
        Linux, such as XMMS, have built-in graphic equalizers. If you are using one of
        these players to preview the "before" and "after" of
        frequency filtering, make sure that all the equalizer knobs are set to a
        central position. Otherwise, the "after" file that sounds best on
        your own system may not sound that good on someone else's system, defeating
        altogether the purpose of doing this kind of processing.



        Sound Effects: Chorus, Delay, Echo, Reverb, Stereo Offset



        Sound effects are even more complex than
        frequency filtering; they include such well-known effects (especially in
        electronic music) as reverberation, echo, delay, flanging, and chorus. The SOX
        utility can add all of these effects to any uncompressed sound file, using the
        same syntax as earlier:



        $ sox mysong.wav -e reverb 1.0 500 250 mysong


        Did I mention that audacity can apply effects
        to all or part of a file, as well? There's more than one way to do it in the
        Linux world.



         





        The Sounds Panel









        The Sounds Panel


        SoundsPanel implements a JPanel that draws a white background and four images. The interesting part of the code is the setting up and use of the images' hot spots (rectangular areas the same size as each image). If a mouse press is inside one of the hot spots, then LoadersTests' playClip( ) plays the associated clip.


        The SoundsPanel constructor stores a reference to LoadersTests, calls initImages( ), and sets up the MouseListener to call selectImage( ):



        // globals
        private static final int PWIDTH = 350; // size of this panel
        private static final int PHEIGHT = 350;

        private LoadersTests topLevel;


        public SoundsPanel(LoadersTests sts)
        { topLevel = sts;
        setPreferredSize( new Dimension(PWIDTH, PHEIGHT) );
        initImages( );
        addMouseListener( new MouseAdapter( ) {
        public void mousePressed( MouseEvent e)
        { selectImage( e.getX( ), e.getY( )); }
        } );
        }



        initImages( ) uses ImagesLoader to load the four GIFs, whose names are hard-wired into the code in the names[] array. The width and height of each image is used to build the array of Rectangle objects that represent the hot spots:



        // globals
        // clip image names
        private final static String[] names = {"dog", "cat", "sheep", "chicken"};

        // on-screen top-left coords for the images
        private final static int[] xCoords = {20, 210, 20, 210};
        private final static int[] yCoords = {25, 25, 170, 170};

        // location of image and sound info
        private final static String IMS_FILE = "imagesInfo.txt";

        private int numImages;
        private BufferedImage[] images;
        private Rectangle[] hotSpots;
        // a click inside these triggers the playing of a clip

        private void initImages( )
        // load and initialise the images, and build their "hot spots"
        {
        numImages = names.length;
        hotSpots = new Rectangle[numImages];
        images = new BufferedImage[numImages];

        ImagesLoader imsLoader = new ImagesLoader(IMS_FILE);

        for (int i=0; i < numImages; i++) {
        images[i] = imsLoader.getImage(names[i]);
        hotSpots[i] = new Rectangle( xCoords[i], yCoords[i],
        mages[i].getWidth( ), images[i].getHeight( ));
        // use images' dimensions for the size of the rectangles
        }
        }



        Each hot-spot rectangle is defined by a top-left coordinate, taken from the xCoords[] and yCoords[] arrays and from a width and height obtained from the loaded image. paintComponent( ) draws the images in the panel using the same xCoords[] and yCoords[] data as the hot-spot rectangles, thereby ensuring that they occupy the same spaces.


        selectImage( ) tries to find the hot spot containing the mouse press coordinates. A matching hot spot's index position in hotSpots[] is used to retrieve a clip name from names[]. playClip( ) is passed the name and the index:



        private void selectImage(int x, int y)
        /* Work out which image was clicked on (perhaps none),
        and request that its corresponding clip be played. */
        {
        for (int i=0; i < numImages; i++)
        if (hotSpots[i].contains(x,y)) { // (x,y) inside hot spot?
        topLevel.playClip(names[i], i); // play that name's clip
        break;
        }
        }



        Back in LoadersTests, playClip( ) is defined as:



        public void playClip(String name, int i)
        // called from SoundsPanel to play a given clip (looping or not)
        { clipsLoader.play(name, clipLoops[i]); }



        The index parameter is employed to look inside clipLoops[] to get the playing mode. This coding approach works because I've ensured that the clipLoops[] array refers to the clips in the same order as the arrays in SoundsPanel.









          Recipe 21.3. Profiling with a Debugger Extension










          Recipe 21.3. Profiling with a Debugger Extension



          21.3.1. Problem


          You want a

          robust solution for profiling your applications so that you can continually monitor where the program spends most of its time.




          21.3.2. Solution


          Use a profiling and debugging extension such as the

          Advanced PHP Debugger (APD) or Xdebug, both available from the PECL repository.


          With APD installed, adding apd_set_pprof_trace( )
          to the top of your script dumps a trace file in a configurable directory. Parsing that trace file gives you a breakdown of how time was spent during that run of the PHP script:


          <?php
          $dumpdir = '/tmp';
          $processid = posix_getpid();
          ini_set('apd.dumpdir', $dumpdir);

          // Prepare to output a basic report
          $dumpfile = $dumpdir . '/pprof.' . $processid . '.0';

          // Start the trace
          apd_set_pprof_trace();

          // Functions that we will profile
          function pc_longString() {
          return uniqid(php_uname('a'), true);
          }

          function pc_md5($str) {
          return md5($str);
          }

          function pc_mhashmd5($str) {
          return bin2hex(mhash(MHASH_MD5, $str));
          }

          function pc_hashmd5($str) {
          return hash('md5', $str);
          }

          // Run the functions
          $str = pc_longString();

          $md5 = function_exists('md5') ? pc_md5($str) : false;
          $md5 = function_exists('mhash') ? pc_mhashmd5($str) : false;
          $md5 = function_exists('hash') ? pc_hashmd5($str) : false;

          echo "now run:\n";
          echo " /usr/bin/pprofp -R $dumpfile\n";
          echo "to view a report.\n";



          Running the report generated by the pprofp tool, which is installed as part of the APD package, results in something like this:


          % /usr/bin/pprofp -R /tmp/pprof.16704.0

          Trace for /home/clay/phpckbk2/apd/md5.php
          Total Elapsed Time = 0.00
          Total System Time = 0.00
          Total User Time = 0.00


          Real User System secs/ cumm
          %Time (excl/cumm) (excl/cumm) (excl/cumm) Calls call s/call Memory Usage Name
          --------------------------------------------------------------------------------------
          100.0 0.00 0.00 0.00 0.00 0.00 0.00 1 0.0005 0.0042 0 main
          77.8 0.00 0.00 0.00 0.00 0.00 0.00 1 0.0033 0.0033 33554432
          apd_set_pprof_trace
          4.6 0.00 0.00 0.00 0.00 0.00 0.00 1 0.0000 0.0002 0 pc_longString
          2.6 0.00 0.00 0.00 0.00 0.00 0.00 1 0.0001 0.0001 0 php_uname
          2.3 0.00 0.00 0.00 0.00 0.00 0.00 1 0.0000 0.0001 0 pc_mhashmd5
          1.5 0.00 0.00 0.00 0.00 0.00 0.00 1 0.0001 0.0001 0 uniqid
          1.5 0.00 0.00 0.00 0.00 0.00 0.00 1 0.0000 0.0001 0 pc_md5
          1.5 0.00 0.00 0.00 0.00 0.00 0.00 1 0.0001 0.0001 0 mhash
          1.3 0.00 0.00 0.00 0.00 0.00 0.00 1 0.0001 0.0001 0 md5
          1.3 0.00 0.00 0.00 0.00 0.00 0.00 3 0.0000 0.0000 0 function_exists
          1.2 0.00 0.00 0.00 0.00 0.00 0.00 1 0.0000 0.0001 0 pc_hashmd5
          1.0 0.00 0.00 0.00 0.00 0.00 0.00 1 0.0000 0.0000 0 hash
          0.6 0.00 0.00 0.00 0.00 0.00 0.00 1 0.0000 0.0000 0 bin2hex





          21.3.3. Discussion


          With APD installed, it's a simple matter to start a profiling session that will store reporting on application runtime. The output files generated by APD can be stored anywhere you want them'even in a dynamic location, if you want to integrate some conditional trace executions into your script. Just use ini_set('apd.dumpdir', '/path/to/writable/dump/directory') to pick a dump location prior to calling apd_set_pprof_trace( ).


          The pprof output file is a machine-readable breakdown of how your script was processed. The output file is stored in the apd.dumpdir location with a naming convention of pprof.process ID.file number. The file number portion of the dump file is determined internally by APD, which will create sequential files as needed for each process being traced.


          Process the output files with the bundled
          pprofp shell application to get some basic insight into what's taking the most time in your application. The longest-running functions are good places to start when looking for opportunities to optimize.


          Beyond basic reporting on execution time, the pprof files can be converted to Kcachegrind-compatible files using the
          pprof2calltree
          conversion tool.
          Kcachegrind is a GUI application used to drill down deeply into applications to determine where bottlenecks are occurring.


          A number of profiling extensions exist; for the most effective debugging and profiling experience, it's recommended to give each one a try to see which one suits your needs the best.




          21.3.4. See Also


          Documentation for APD at http://www.php.net/manual/en/ref.apd.php; the Xdebug profiling and debugging extension at http://www.xdebug.org/; the DBG extension at http://dd.cron.ru/dbg/; the Kcachegrind profiling visualization tool at http://kcachegrind.sourceforge.net.













          Arrays













          Programming in Lua
          Part II. Tables and Objects
                      
          Chapter 11. Data Structures



          11.1 - Arrays



          We implement arrays in Lua simply by indexing tables with integers.
          Therefore, arrays do not have a fixed size,
          but grow as we need.
          Usually, when we initialize the array we define
          its size indirectly.
          For instance, after the following code


          a = {} -- new array
          for i=1, 1000 do
          a[i] = 0
          end

          any attempt to access a field outside the range 1-1000
          will return nil, instead of zero.


          You can start an array at index 0, 1, or any other value:


          -- creates an array with indices from -5 to 5
          a = {}
          for i=-5, 5 do
          a[i] = 0
          end

          However, it is customary in Lua to start arrays with index 1.
          The Lua libraries adhere to this convention;
          so, if your arrays also start with 1,
          you will be able to use their functions directly.

          We can use constructors to create and initialize arrays in a
          single expression:


          squares = {1, 4, 9, 16, 25, 36, 49, 64, 81}

          Such constructors can be as large as you need
          (well, up to a few million elements).










          Programming in Lua



          Implementing Listeners in the quartz_jobs.xml File










          Implementing Listeners in the quartz_jobs.xml File


          All the examples in this chapter have shown how to set up listeners using a programmatic approach. This chapter wouldn't be complete if we didn't provide at least an example of configuring a listener using a declarative approach with the quartz_jobs.xml file.


          Starting with Quartz 1.5, you are able to specify listeners in the job-definition file, otherwise known as the quartz_jobs.xml file. Listing 7.14 shows an example of using a global listener.


          Listing 7.14. Quartz Listeners Can Be Implemented with the quartz_jobs.xml File






          <?xml version='1.0' encoding='utf-8'?>

          <quartz>
          <job-listener
          class-name="org.cavaness.quartzbook.chapter7.SimpleJobListener"
          name="SimpleJobListener">
          </job-listener>

          <job>
          <job-detail>
          <name>PrintInfoJob</name>
          <group>DEFAULT</group>
          <job-listener-ref>SimpleJobListener</job-listener-ref>
          <job-class>
          org.cavaness.quartzbook.common.PrintInfoJob
          </job-class>
          </job-detail>

          <trigger>
          <simple>
          <name>printJobTrigger</name>
          <group>DEFAULT</group>
          <job-name> PrintInfoJob</job-name>
          <job-group>DEFAULT</job-group>
          <start-time>2005-09-13 6:10:00 PM</start-time>
          <! repeat indefinitely every 10 seconds >
          <repeat-count>-1</repeat-count>
          <repeat-interval>10000</repeat-interval>
          </simple>
          </trigger>
          </job>
          </quartz>




          You see in Listing 7.14 the additional <job-listener> element with the two required attributes:


          <job-listener
          class-name="org.cavaness.quartzbook.chapter7.SimpleJobListener"
          name="SimpleJobListener">


          The class-name property identifies the fully qualified name of the listener class. The name attribute assigns a logical name to the listener used in the <job-detail> element.


          The next step is to define a <job-listener-ref> element in the <job-detail> element in the same file for each job that you want the listener on. The value of the element must match the name property of one of the defined <job-listener> elements in the file.


          After you have done that, make sure you've configured the Scheduler to use the JobInitializationPlugin by setting the properties in the quartz.properties file. Quartz plug-ins are discussed in detail in the next chapter. For now, just add the following lines to your quartz.properties file:


          org.quartz.plugin.jobInitializer.class =
          org.quartz.plugins.xml.JobInitializationPlugin

          org.quartz.plugin.jobInitializer.overWriteExistingJobs = true
          org.quartz.plugin.jobInitializer.failOnFileNotFound = true
          org.quartz.plugin.jobInitializer.validating=false


          Then name your XML file quartz_jobs.xml and put the file in your classpath.




          Some "Gotchas" to Watch Out For


          It's worth mentioning a couple problems that you will likely run into when trying to set up listeners with the XML file. In Quartz 1.5, at least, the setName() method for the listeners was not included in the interface. The getName() method is present, but not the corresponding setName(). This doesn't seem to cause a problem when using listeners programmatically, but it will with the declarative approach. You simply need to create a setName() method for your listener.


          The other tip is to make sure you have a no-arg constructor for your listener. Under certain conditions, the Quartz framework won't complain, but when using this declarative approach, you will get an error. It's better just to declare the no-arg constructor and always be safe.














          Puzzle 78: Reflection Infection











           < Day Day Up > 







          Puzzle 78: Reflection Infection



          This puzzle illustrates a simple application of reflection. What does this program print?





          import java.util.*;

          import java.lang.reflect.*;



          public class Reflector {

          public static void main(String[] args) throws Exception {

          Set<String> s = new HashSet<String>();

          s.add("foo");

          Iterator it = s.iterator();

          Method m = it.getClass().getMethod("hasNext");

          System.out.println(m.invoke(it));

          }

          }














          Solution 78: Reflection Infection



          The program creates a set with a single element in it, gets an iterator over the set, invokes the iterator's hasNext method reflectively, and prints the result of the method invocation. As the iterator hasn't yet returned the set's sole element, hasNext should return TRue. Running the program, however, tells a different story:





          Exception in thread "main" IllegalAccessException:

          Class Reflector can not access a member of class HashMap

          $HashIterator with modifiers "public"

          at Reflection.ensureMemberAccess(Reflection.java:65)

          at Method.invoke(Method.java:578)

          at Reflector.main(Reflector.java:11)




          How can this be? Of course the hasNext method is public, just as the exception tells us, and so can be accessed from anywhere. So why should the reflective method invocation be illegal?



          The problem isn't the access level of the method; it's the access level of the type from which the method is selected. This type plays the same role as the qualifying type in an ordinary method invocation [JLS 13.1]. In this program, the method is selected from the class represented by the Class object that is returned by it.getClass. This is the dynamic type of the iterator, which happens to be the private nested class java.util.HashMap.KeyIterator. The reason for the IllegalAccessException is that this class is not public and comes from another package: You cannot legally access a member of a nonpublic type from another package [JLS 6.6.1].



          This prohibition applies whether the access is normal or reflective. Here is a program that runs afoul of this rule without resorting to reflection:





          package library;

          public class Api {

          static class PackagePrivate {}

          public static PackagePrivate member = new PackagePrivate();

          }



          package client;

          import library.Api;

          class Client {

          public static void main(String[] args) {

          System.out.println(Api.member.hashCode());

          }

          }




          Attempting to compile the program results in this error:





          Client.java:5: Object.hashCode() isn't defined in a public

          class or interface; can't be accessed from outside package

          System.out.println(Api.member.hashCode());

          ^




          This diagnostic makes about as much sense as the runtime error generated by the original reflective program. The class Object and the method hashCode are both public. The problem is that the hashCode method is invoked with a qualifying type that is inaccessible to the client. The qualifying type of the method invocation is library.Api.PackagePrivate, which is a nonpublic class in a different package.



          This does not imply that Client can't invoke hashCode on Api.member. To do this, it has merely to use an accessible qualifying type, which it can do by casting Api.member to Object. With this change, Client compiles and runs successfully:





          System.out.println(((Object)Api.member).hashCode());




          As a practical matter, this problem doesn't arise in ordinary nonreflective access, because API writers use only public types in their public APIs. Even if the problem were to occur, it would manifest itself as a compile-time error, so it would be fixed quickly and easily. Reflective access is another matter. Although common, the idiom object.getClass().getMethod("methodName") is broken and should not be used. It can easily result in an IllegalAccessException at run time, as we saw in the original program.



          When accessing a type reflectively, use a Class object that represents an accessible type. Going back to our original program, the hasNext method is declared in the public type java.util.Iterator, so its class object should be used for reflective access. With this change, the Reflector program prints TRue as expected:





          Method m = Iterator.class.getMethod("hasNext");




          You can avoid this whole category of problem if you use reflection only for instantiation and use interfaces to invoke methods [EJ Item 35]. This use of reflection isolates the class that invokes methods from the class that implements them and provides a high degree of type-safety. It is commonly used in Service Provider Frameworks. This pattern does not solve every problem that demands reflective access, but if it solves your problem, by all means use it.



          In summary, it is illegal to access a member of a nonpublic type in a different package, even if the member is also declared public in a public type. This is true whether the member is accessed normally or reflectively. The problem is likely to manifest itself only in reflective access. For platform designers, the lesson, as in Puzzle 67, is to make diagnostics as clear as possible. Both the runtime exception and the compiler diagnostic leave something to be desired.

























             < Day Day Up > 



            7.3 Type-Enforcement Declarations











             < Day Day Up > 







            7.3 Type-Enforcement Declarations





            Type-enforcement (TE) declarations are of seven types:






            attribute_def





            Attribute declarations






            type_def





            Type declarations






            typealias_def





            Type alias declarations






            bool_def





            Boolean declarations






            transition_def





            Transition declarations






            te_avtab_def





            TE access vector table declarations






            cond_stmt_def





            Conditional statement declarations











            7.3.1 Type Declarations





            The SELinux policy language requires that

            all type names be explicitly defined. In the simplest possible form,

            a type declaration merely defines a name as a type. For instance, the

            type declaration:





            type ping_t;







            would mark ping_t as the name of a type. Type

            declarations need not precede all statements that refer to the types

            they define; you can place type declarations any place within a TE

            file.





            Optionally, a type declaration may define one or more

            aliases for the type name. Any

            alias associated with a type can be freely used in place of the

            primary name of the type. A type declaration can also optionally

            associate one or more attributes with the type name.





            Figure 7-1 shows the syntax of a type declaration.

            As an example, the ping.te file contains two

            type declarations:





            type ping_t, domain, privlog;

            type ping_exec_t, file_type, sysadmfile, exec_type;







            The first declaration identifies ping_t as a type

            name, and associates the attributes domain and

            privlog with the type name, marking the type as a

            domain that communicates with the system log process. The second

            declaration identifies ping_exec_t as a type name,

            and associates the attributes file_type,

            sysadmfile, and exec_type with

            the type name, marking the type as one used to identify executable

            files accessible by system administrators.







            Figure 7-1. Type declaration (type_def)







            To better understand how type attributes work with types, consider

            the definition of the

            syslogd domain, which contains the following

            declarations:





            allow privlog devlog_t:sock_file { ioctl read getattr lock write append };

            allow privlog syslogd_t:unix_dgram_socket sendto;

            allow privlog syslogd_t:unix_stream_socket connectto;

            allow privlog devlog_t:lnk_file read;







            Notice how the type attribute privlog

            is used in these declarations in the same way that an actual type

            name might be used. Type attributes differ from types in that type

            attributes generally appear in multiple domains, whereas each type

            generally appears only in a single domain. You can think of a type

            attribute as simply an abbreviation standing for a set of access

            vector rules. You can associate these access vector rules with a type

            simply by binding the type attribute with the type, just as the

            domain and privlog type

            attributes are bound to the ping_t type.





            The four allow declarations given earlier specify

            the range of permissible operations associated with the

            privlog type attribute, specifically:





            • Perform various read and write operations on socket files having type

              devlog_t.

            • Send data to datagram and stream sockets having type

              syslogd_t.

            • Read files and symbolic links having type devlog_t.



            As you'd likely guess, the types

            devlog_t and syslogd_t are used

            to label system log files, system log FIFOs, and the sockets used to

            communicate with the syslog process.







            The meanings of type attributes such as domain and

            privlog are not hardcoded in SELinux. Instead, the

            meaning of a type attribute is determined by policy statements.

            Consequently, the administrator of an SELinux system can create new

            type attributes or modify the meaning of type attributes that appear

            in sample policies. If the administrator of an SELinux system has

            added or modified many type attributes, it may be difficult to

            determine their meanings, as doing so would involve reading all the

            policy declarations related to each customized type attribute.





            Fortunately, the set of type attributes defined in sample policies is

            rich, and system administrators generally do not need, or choose, to

            extend or modify it substantially. And most domain attributes have

            names that suggest their meaning. Appendix E, explained in the

            upcoming section titled "Attribute

            Declarations," summarizes the meanings of principal

            SELinux type attributes.












            7.3.2 Type-Alias Declarations





            As explained

            in the preceding section, a type

            declaration can optionally bind one or more aliases to a type name.

            However, it's more common to use a special

            type-alias declaration to establish such a binding. Figure 7-2 shows the syntax of type-alias declarations.







            Figure 7-2. Type-alias declaration (typealias_def)







            Many M4 macros generate

            type alias declarations. However, a few TE files contain explicit

            type-alias declarations. For instance, the

            cups.te file contains the follow type-alias

            declaration:





            typealias cupsd_etc_t alias etc_cupsd_t;







            This declaration defines etc_cupsd_t as an alias

            for the type name cupsd_etc_t, allowing the two

            names to be used interchangeably.









            7.3.3 Attribute Declarations





            A type attribute is a name that is

            bound to one or more types and used to define a set of types sharing

            some property. For instance, a type attribute can be used to

            designate the types (domains) that are allowed to read the system log

            file.





            Because type attributes can appear in allow

            declarations just as though they were types, permissions can be

            granted by referring either to types or type attributes. An

            allow declaration containing a type attribute

            refers to all types associated with the type attribute. Thus, type

            attributes make it convenient to specify policies that apply to

            multiple types. The relationship between types and attributes is a

            many-to-many relationship; an indefinite number of types can be

            associated with an attribute, and an indefinite number of attributes

            can be associated with a type.





            Type attributes are defined in the file attrib.te.

            Appendix E

            summarizes the type attributes defined in the Fedora

            Core 2 implementation of SELinux.





            Figure 7-3 shows the syntax of an attribute

            declaration, the SELinux policy statement that defines a type

            attribute. As you can see, the syntax is quite simple. A typical

            declaration is:





            attrib admin;







            This declaration identifies admin as an attribute.

            Appendix E explains that this attribute is used to identify

            administrator domain�domains that should be available only to

            system administrators.







            Figure 7-3. Attribute declaration (attribute_def)









            Recall that the term domain refers to a type

            associated with a process.












            7.3.4 TE Access-Vector Declarations





            The permissions enforced by the SELinux security

            engine are held in kernel data space in an object known as the TE

            access matrix. As explained in Chapter 2, the

            TE access matrix includes four distinct access components, called

            vectors:






            allow





            Operations that are allowed but are not

            logged






            auditallow





            Operations that are allowed and are

            logged when they occur






            auditdeny





            Operations that are denied and are logged

            when they are attempted






            dontaudit





            Operations that are denied, but are not

            logged when they are attempted









            Each TE access vector contains TE access-vector rules. A TE

            access-vector rule specifies permissible operations�based on a

            source type, a target type, and a security object class. Whenever an

            operation is attempted, the SELinux security engine searches the

            access vectors for a rule matching the source type, target type, and

            object class of the operation. If a matching rule is found, the

            access vector containing the rule determines the action taken by

            SELinux. For instance, if the matching rule resides in the

            allow access vector, the operation is allowed.

            However, if the matching rule resides in another access vector, or no

            matching rule exists, the operation is denied.





            Figure 7-4 shows the syntax of

            access-vector rules. Notice that the

            diagram shows what seems to be a fifth type of access-vector rule,

            represented by the

            neverallow rule type. The

            neverallow rule defines constraints that the

            SELinux policy must observe. The policy compiler checks for

            violations of these constraints, and if it finds any violations, it

            terminates without producing a binary policy file. You can add or

            subtract neverallow rules from the SELinux policy.

            However, they're intended as a safety feature that

            prevents you from generating a grossly insecure policy, so

            it's generally best not to disturb them.







            Figure 7-4. TE access vector rule declaration (te_avtab_def)







            Each of the five forms of access vector rules contains four terms:





            • The source type or types; this is generally the type associated with

              the process attempting to perform an operation.

            • The target type or types; this is generally the type associated with

              the object that the process is attempting to manipulate.

            • The object class or classes to which the rule applies.

            • The permissions that the rule establishes.



            The syntax of each of these terms is represented by the replaceable

            text names, which was explained in Chapter 6 and represented in Figure 6-13.





            Here's a sample allow

            declaration associated with the

            ping_t domain:





            allow ping_t ping_exec_t:file { read getattr lock execute ioctl };







            The rule created by this declaration allows processes running in the

            ping_t domain to perform any of five operations

            (read, getattr,

            lock, execute, and

            ioctl) on files labeled as belonging to the

            ping_exec_t domain.







            If you check the ping.te file, you

            won't find this declaration there. Many

            access-vector declarations, including this one, are created by

            expansion of M4 macros, such as the

            domain_auto_trans macro explained later in this

            section.








            The standard SELinux security policy includes fewer than six

            auditallow

            declarations. Here's a sample declaration:





            auditallow kernel_t security_t:security load_policy;







            Recall that auditallow rules

            don't actually enable any operations. Therefore,

            this rule is supplemented by an allow rule such

            as:





            allow kernel_t security_t:security load_policy;







            The allow rule authorizes processes running in the

            kernel_t domain (that is, kernel processes) to

            perform the load_policy operation on

            security objects labeled with the

            security_t domain. More plainly, the

            allow rule allows the kernel to load an SELinux

            policy. The auditallow rule causes every such

            operation to be logged when it is performed. Thus, the system log

            contains a record of these important events.





            The standard SELinux security policy does not include even one

            instance of an auditdeny rule. Since the default

            action of SELinux is to forbid unauthorized operations and make a log

            entry documenting the action,

            auditdeny

            rules are not generally needed. However, so that you can see how

            auditdeny rules work, here's a

            hypothetical auditdeny rule declaration:





            auditdeny user_t security_t:security load_policy;







            The rule created by this declaration forbids processes running in the

            user_t domain from performing the

            load_policy operation on

            security objects labeled with the

            security_t domain.





            Here's a sample declaration of a

            dontaudit rule:





            dontaudit ping_t var_t:dir search;







            The rule created by this declaration suppresses log entries when

            processes in the ping_t domain attempt to search a

            directory labeled with the var_t domain, and are

            prohibited by the SELinux security engine from doing so.







            It's somewhat common for programs to attempt

            operations on security-sensitive objects, even though they

            don't need to do so. The

            dontaudit rule enables you to suppress such

            operations and avoid cluttering the log with a flood of routine

            entries associated with them.








            As explained, the

            neverallow

            rule type enforces constraints on the SELinux security policy itself.

            It helps ensure the integrity of the policy, which might be

            inadvertently weakened by well-intentioned but erroneous changes.

            Operations forbidden by a neverallow constraint

            are prohibited even if a conflicting

            allow rule exists within the

            SELinux security policy
            .





            Here's a hypothetical neverallow

            constraint declaration:





            neverallow domain file_type:process transition;







            The constraint created by this declaration would prevent a process

            having the domain attribute from transitioning to

            a type having the file_type attribute. The

            constraint would prevent an errant policy modification that allowed a

            process to be treated as a file, which might compromise system

            security.







            7.3.4.1 Special notations for types, classes, and permissions




            The hypothetical

            neverallow constraint just given is effective but

            incomplete. Ideally, we'd prohibit transitions from

            a domain type to any non-domain

            type, not just every type marked as a file_type. A

            special notation associated with the replaceable text

            names enables us to do so:





            neverallow domain ~domain:process transition;







            The constraint associated with this declaration forbids a process

            having the domain type attribute from

            transitioning to a type not having that attribute. For instance, the

            constraint prevents a malicious user from causing a process to

            transition to a file or another nondomain object.





            Notice that the target type is specified as

            ~domain. This notation, known as

            complementation,

            provides a convenient means of referring to types that do

            not
            possess a specified attribute. In this case, the

            declaration refers to types that do not have the

            domain attribute. If complementation were not

            available, we'd find it cumbersome to write a

            constraint such as this, since the constraint would have to refer

            explicitly to every type that is not a domain. Many such types might

            exist. Moreover, having added a new nondomain type to the policy, we

            might neglect to modify the constraint appropriately. So

            complementation provides an important convenience.





            Another convenient notation is known as

            subtraction.

            Here's an example of a constraint declaration that

            employs subtraction:





            neverallow { domain -admin -anaconda_t -firstboot_t -unconfined_t -kernel_t          

            -load_policy_t } security_t:security load_policy;







            The constraint created by this declaration prevents any domain other

            than those listed with minus signs (admin,

            anaconda, firstboot_t,

            unconfined_t, kernel_t, and

            load_policy_t) from performing the

            load_policy operation on a

            security object having type

            security_t.





            Occasionally, it's necessary to refer to

            all types, classes, or permissions. The asterisk

            (*) can be used to do so, as in the following constraint declaration:





            neverallow domain file_type:process *;







            The constraint created by this declaration prohibits any type having

            the domain attribute from performing

            any operation on processes having the

            file_type attribute.





            Here's a somewhat more interesting example that

            includes two instances of the asterisk operator:





            neverallow ~{ domain unlabeled_t } *:process *;







            The constraint created by this declaration prevents types other than

            those having attributes domain or

            unlabeled_t from performing

            any operation on processes having

            any type.





            Another special notation enables us to create rules where the target

            type is the same as the source type. Here's an

            example:





            neverallow {domain -admin -insmod_t -kernel_t -anaconda_t -firstboot_t -unconfined_t } 

            self:capability sys_module;







            The rule created by this declaration applies to domains other than

            six specific domains (admin,

            anaconda, firstboot_t,

            unconfined_t, kernel_t, and

            load_policy_t). It prohibits these domains from

            performing the sys_module operation on

            capability objects labeled with domains other than

            the source domain.





            These special notations can be used with allow

            rules as well as neverallow rules. For instance,

            consider the following rule:





            allow sysadm_t self:process ~{ ptrace setexec setfscreate setrlimit };







            This rule lets processes within the sysadm_t

            domain perform any operation on processes running within that domain,

            with the exception of the operations listed:

            ptrace, setexec,

            setfscreate, and setrlimit.





            Table 7-1 summarizes the special notations used to

            specify types, classes, and permissions.





            Table 7-1. Special notations for specification of types, classes, and permissions


            Notation





            Description





            *







            All members





            ~







            Complementation





            -







            Subtraction





            self







            Target type same as source type










            In addition to special notations, macros can be used to specify

            types, classes, or permissions.

            Appendix C summarizes a set of such

            macros, defined in the file

            macros/core_macros.te.







            It's not necessary to specify all authorized

            permissions in a single access-vector rule. SELinux combines

            permissions pertaining to the same source type, target type, and

            object class into a single access-vector rule that authorizes all

            specified operations.














            7.3.4.2 Macros that specify and authorize transitions




            Two main types of rules govern transitions:






            Type-transition rules





            Specify



            transitions that occur

            when a new object, such as a process or file, is created.






            Access-vector rules





            Authorize



            transitions.









            Type-transition rules do not authorize the transitions they specify.

            That is, they specify the transition that would

            occur, but don't actually give permission for the

            transition to occur. An access-vector rule must authorize the

            transition, or it will not be allowed to occur. Therefore, type

            transition and access vector rules both must be specified for most

            transitions. To avoid the associated tedium, several M4 macros

            conveniently generate type transition and access vector rule

            declarations from a single line of policy source code. Generally, the

            most useful of these macros are:






            domain_auto_trans





            Specifies and authorizes a transition

            related to the execution of a program defined as a domain entry

            point.






            file_type_auto_trans





            Specifies and authorizes a transition

            related to file creation.









            For instance, the ping.te file of the

            Fedora Core 2 SELinux implementation invokes the

            domain_auto_trans macro three times:





            domain_auto_trans(unpriv_userdomain, ping_exec_t, ping_t)

            domain_auto_trans(sysadm_t, ping_exec_t, ping_t)

            domain_auto_trans(initrc_t, ping_exec_t, ping_t)







            The first invocation is executed conditionally, as explained in the

            next section. The second and third invocations are executed

            unconditionally. Each invocation defines a transition from a domain

            (unpriv_userdomain, sysadm_t,

            or initrc_t) to the ping_t

            domain when a ping_exec_t executable is loaded.

            The transition is also authorized by an access vector rule. For

            instance, the third invocation expands to the following policy

            declarations:





            type_transition initrc_t ping_exec_t:process ping_t;

            allow initrc_t ping_t:process transition;







            Here's an example of a typical use of the

            file_type_auto_trans macro, occurring in the

            ftpd.te file of the Fedora Core 2 SELinux

            implementation:





            file_type_auto_trans(ftpd_t, var_log_t, xferlog_t, file)







            This macro invocation expands to the following policy declarations:





            type_transition ftpd_t var_log_t:file xferlog_t;

            allow ftpd_t var_log_t:dir rw_dir_perms;

            allow ftpd_t var_log_t:file create_file_perms;







            The file_type_auto_trans macro simplifies

            definition of the ftpd_t domain, by using a

            one-line macro invocation to specify that:





            • When an ftpd_t process creates a file in a

              directory having type var_log_t (such as

              /var/log), the file should be given the type

              xferlog_t. Thus, the FTP logs

              /var/log/xferlog and

              /var/log/xferreport will be properly labeled

              when created.

            • Any ftpd_t process can read and write

              var_log_t directories (that is, perform any of the

              following operations associated with rw_dir_perms:

              read, getattr,

              lock, search,

              ioctl, add_name,

              remove_name, and write).

            • Any ftpd_t process can create files within

              var_log_t directories (that is, perform any of the

              following operations associated with

              create_file_perms: create,

              ioctl, read,

              getattr, lock,

              write, setattr,

              append, link,

              unlink, and rename).



            Occasionally, it's convenient to specify, but not

            authorize, a transition because the transition is already authorized

            elsewhere in the policy file or in another policy file. The following

            macros do so:






            domain_trans





            Specifies, but does not authorize, a

            transition related to execution of a program defined as a domain

            entry point.






            file_type_trans





            Specifies, but does not authorize, a

            transition related to file creation.















            7.3.5 Transition Declarations





            A transition rule specifies the

            new domains for a process or the security contexts for a newly

            created object, such as a file. Each transition rule has two types: a

            source type and a target type. For a process, the source type is the

            current domain of the process, and the target type is the type of the

            executable file. For an object, the source type is the domain of the

            process creating the object, and the target type is the type of a

            related object. For instance, if the object is a file, the target

            type is the type of the file's parent directory.





            Figure 7-5 shows the syntax of

            type transitions. The railroad diagram

            contains three instances of replaceable text, each having the

            syntax of the now-familiar replaceable text names,

            originally described in Chapter 6 and

            represented in Figure 6-13:





            • The source type or types

            • The target type or types

            • The object class or classes to which the transition rule applies



            The diagram also includes the replaceable text

            new_type, which has the syntax of the familiar

            replaceable text identifier. The replaceable text

            new_type specifies the new type of the process or

            object.







            Figure 7-5. Transition declarations (transition_def)







            Here's a typical type transition rule pertaining to

            a process:





            type_transition sysadm_t ping_exec_t:process ping_t;







            This rule affects the behavior of processes in the

            sysadm_t domain that execute a program having type

            ping_exec_t. Executing such a program causes the

            process to attempt to transition to the

            ping_t domain. I write attempt

            to
            because SELinux does not authorize operations,

            including transitions, by default. So if the transition is to

            succeed, an access-vector rule must authorize it; otherwise, unless

            SELinux is operating in permissive mode, the SELinux security engine

            will prohibit the transition.





            Here's a typical type-transition rule pertaining to

            a file:





            type_transition httpd_t var_log_t:file httpd_log_t;







            This rule affects the behavior of processes in the

            httpd_t domain that create a file having a parent

            directory of the var_log_t type. Such files are

            created with the httpd_log_t type, unless the

            appropriate access vector rule does not exist.





            The replaceable text identifier is always

            associated with a single identifier, whereas the replaceable text

            names can be associated with multiple identifiers,

            as shown in Figure 6-13. Because the railroad

            diagram refers to three instances of names and one

            instance of identifier�rather than four

            instances of identifier�a transition

            declaration can refer to multiple source types, target types, or

            classes. Here's a typical rule that does so:





            type_transition httpd_t tmp_t:{ file lnk_file sock_file fifo_file } httpd_tmp_t;







            Like the preceding rule, this rule also affects the behavior or

            processes in the httpd_t domain. When such a

            process creates a file,

            lnk_file, sock_file, or

            fifo_file object having a parent object of type

            tmp_t, the new object receives the type

            http_tmp_t, unless the appropriate access vector

            rule does not exist.





            Because several sets of class names are commonly used, the file

            macros/



            core_macros.te

            defines eight convenient M4 macros, described in Table 7-2. Using the appropriate macro, the preceding

            type transition rule could be written more compactly as:





            type_transition httpd_t tmp_t:notdevfile_class_set httpd_tmp_t;







            Table 7-2. Class name M4 macros


            Macro





            Definition





            Description





            devfile_class_set







            { chr_file blk_file }







            Device file classes





            dgram_socket_class_set







            { udp_socket unix_dgram_socket }







            Datagram socket classes





            dir_file_class_set







            { dir file lnk_file sock_file fifo_file chr_file blk_file }







            Directory and file classes





            file_class_set







            { file lnk_file sock_file     fifo_file chr_file blk_file }







            File classes except dir





            notdevfile_class_set







            { file lnk_file sock_file     fifo_file }







            File classes except dir and device files

            (chr_file, blk_file)





            socket_class_set







            { tcp_socket udp_socket      rawip_socket netlink_socket packet_socket unix_stream_socket unix_dgram_socket }







            Socket classes





            stream_socket_class_set







            { tcp_socket unix_stream_socket }







            Stream socket classes





            unpriv_socket_class_set







            { tcp_socket udp_socket unix_stream_socket unix_dgram_socket }







            Unprivileged socket classes except raw IP socket class












            7.3.6 Boolean Declarations





            The Fedora Core 2 implementation of

            SELinux introduced a new feature: Boolean declarations. A Boolean is

            a true-false value that can be tested by policy statements. As

            explained in Chapter 4, the

            setbool command can

            set the value of a Boolean. Booleans make it possible to tailor

            dynamically the behavior of an SELinux policy.





            Figure 7-6 shows the syntax of a Boolean

            declaration. The Fedora Core 2 SELinux policy defines one Boolean,

            user_ping:





            bool user_ping false;







            This Boolean controls nonprivileged user access to the

            ping

            and traceroute commands. This control is

            implemented by conditional declarations included in the

            ping.te and traceroute.te

            files, as explained in the next section.







            Figure 7-6. Boolean declaration (bool_def)











            7.3.7 Conditional Declarations





            The declarations explained so far in

            this chapter have been unconditional declarations. Recent

            implementations of SELinux, such as that included in Fedora Core 2,

            also support conditional declarations. A simple conditional

            declaration has two parts:





            • A Boolean expression that is evaluated when the security engine makes

              policy decisions.

            • A declaration that takes effect only if the Boolean expression

              evaluates true. The declaration is referred to as a subdeclaration,

              because it occurs inside the conditional declaration.



            A more sophisticated conditional declaration includes a Boolean

            expression and two alternative subdeclarations. Depending on the

            result of dynamically evaluating the Boolean expression, the

            declaration has the force of either of the two subdeclarations.





            Figure 7-7 shows the syntax of a conditional

            declaration. As the figure shows, the syntax of the associated

            conditional expression (cond_expr) is rich. The

            subdeclaration or subdeclarations have a familiar form, that of

            either a type transition or access-vector declaration of the

            following kinds:





            • allow

            • auditallow

            • auditdeny

            • dontaudit





            Although the railroad diagram in Figure 7-7

            indicates that a subdeclaration can be an

            auditdeny declaration, SELinux does not support

            such subdeclarations at the time of writing. However, you can express

            equivalent policies by using one or more other declaration types

            rather than an auditdeny.










            Figure 7-7. Conditional statement declaration (cond_stmt_def)







            The conditional expression within a conditional statement declaration

            can use any of six relational operators, summarized in Table 7-3.





            Table 7-3. Relational operators


            Symbol





            Description





            &&







            Logical AND





            ==







            Logical equality





            !







            Logical negation





            !=







            Logical inequality





            ||







            Logical OR





            ^







            Logical exclusive OR








            Here's a sample conditional statement declaration,

            taken from the ping.te file

            associated with the Fedora Core 2 implementation of SELinux:





            if (user_ping) {

            domain_auto_trans(unpriv_userdomain, ping_exec_t, ping_t)

            # allow access to the terminal

            allow ping_t { ttyfile ptyfile }:chr_file rw_file_perms;

            ifdef(`gnome-pty-helper.te', `allow ping_t gphdomain:fd use;')

            }







            The user_ping conditional expression

            refers to a policy Boolean that indicates whether nonprivileged users

            are authorized to use the ping and

            traceroute commands, as explained earlier in

            this chapter. Only if the Boolean has the value

            true do the subdeclarations have effect. The

            subdeclarations:





            • Authorize an automatic transition from a domain marked as an

              unpriv_userdomain to the ping_t

              domain upon execution of a ping_exec_t program.

            • Authorize the ping_t domain to access the

              user's TTY or PTY.

            • Invoke an M4 macro, ifdef, that conditionally

              allows the ping_t domain to use file descriptions

              passed by the Gnome PTY helper (gphdomain)



              domain.

















               < Day Day Up >