C++ OO design question

Discussion in 'C++' started by indrawati.yahya, Sep 17, 2007.

  1. In a recent job interview, the interviewer asked me how I'd design
    classes for the following problem: let's consider a hypothetical
    firewall, which filters network packets by either IP address, port
    number, or both. How should we design the classes to represent these
    filters?

    My answer was:

    class FilterRule
    {
    public:
    virtual bool Accept(const Packet&) const = 0; //Packet is a
    representation of a network packet
    };
    class FilterByIP: public FilterRule { /* members here */ };
    class FilterByPort: public FilterRule { /* members here */ };

    class Filter
    {
    public:
    bool Accept(const Packet&) const; //returns true if ALL
    filterRules Accept() the Packet
    private:
    std::vector<FilterRule> filterRules;
    };


    However, the interviewer said that he preferred this solution instead:

    class Filter
    {
    public:
    virtual bool Accept(const Packet&) const = 0;
    };
    class FilterByIP: public Filter { /* members here */ }
    class FilterByPort: public Filter { /* members here */ }
    class FilterByIPAndPort: public Filter
    {
    protected:
    FilterByIP ipFilter;
    FilterByPort portFilter;
    /* other members */
    };

    I reasoned that with his solution, there may be too many class numbers
    if down the road we decide to filter packets by methods other than IP
    address and Port, but somehow he was not convinced. Oh well, I didn't
    get the job, but this question continues to haunt me to this day. What
    do you C++ experts think? Or is there another better solution that I
    did not consider? Thank you.
     
    indrawati.yahya, Sep 17, 2007
    #1
    1. Advertisements

  2. indrawati.yahya

    Kai-Uwe Bux Guest

    You mean

    I like your idea of representing a filter just as a vector of filter rules.
    If you want to actually reduce that to practice, you could use duck typing
    instead of inheritance. E.g.:

    typedef bool (sig) (Paket const &)
    typedef std::tr1::function<sig> FilterRule;

    Now, FilterRule can hold any value that supports

    bool operator() ( Paket const & )

    In particular, the concrete classes could be:

    class IpFilterRule {
    ...
    public:

    bool operator() ( Paket const & p ) {
    }

    };

    class PortFilterRule {
    ...
    public:

    bool operator() ( Paket const & p ) {
    }

    };

    and a Filter can now easily be represented as a std::vector< FilterRule >.

    Note that there is no coupling between the classes. Should there be common
    code, one can incorporate that into the classes using private inheritance.
    It would be considered an implementation detail.

    Also, the client code would use objects of type FilterRule (or IpFilterrule,
    etc) instead of FilterRule* (or IpFilterRule*, etc).


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Sep 17, 2007
    #2
    1. Advertisements

  3. This is really a question for a group discussing object-oriented design
    so you should ask in comp.object or perhaps comp.programming.
    Slicing, you cannot store derived types in a vector parametrised by the
    base type, you have to use pointers instead:


    I assume you forgot
    class Filter
    This assumes that you can filter multiple IP addresses or ports with a
    single FilterByIP object, which might allow some optimisations that are
    not possible when you have more than one FilterByIP object (which your
    solution allows). However it is also less flexible for the same reasons.
    Yes, I also prefer your design, it is more flexible and more easily
    extended, however I've never thought much about firewall design and
    there might be some other reasons to use his design.
     
    =?ISO-8859-1?Q?Erik_Wikstr=F6m?=, Sep 17, 2007
    #3
  4. Erik Wikström a écrit :
    IMO in "either IP address, port number, or both.", the "both" means
    ports related to specific IP addresses and not merely applying the rules
    independantely; this makes sense with the interviewer's design and with
    the field.

    Michael
     
    Michael DOUBEZ, Sep 17, 2007
    #4
  5. That can easily be solved with the OP's design by adding a class like
    FilterByIPAndPort, and to be honest I thought that was just an omission
    of the OP (just like leaving out a FilterByIPAndPort member in the
    interviewer's design. I thought the issue was the question if a
    container should be used or members like in the interviewer's design.
     
    =?ISO-8859-1?Q?Erik_Wikstr=F6m?=, Sep 17, 2007
    #5
  6. indrawati.yahya

    Kai-Uwe Bux Guest

    I just realized that one can go even further with this idea:


    #include <tr1/functional>
    #include <vector>
    #include <iostream>

    typedef unsigned int Paket;

    // machinery for predicates
    // ========================

    typedef bool(sig)(Paket const &);
    typedef std::tr1::function<sig> PaketPredicate;

    class AndPredicate {

    PaketPredicate the_lhs;
    PaketPredicate the_rhs;

    AndPredicate ( PaketPredicate const & lhs,
    PaketPredicate const & rhs )
    : the_lhs ( lhs )
    , the_rhs ( rhs )
    {}

    public:

    friend
    AndPredicate operator&& ( PaketPredicate const & lhs,
    PaketPredicate const & rhs );

    bool operator() ( Paket const & p ) const {
    return ( the_lhs(p) && the_rhs(p) );
    }

    };

    AndPredicate operator&& ( PaketPredicate const & lhs,
    PaketPredicate const & rhs ) {
    return ( AndPredicate( lhs, rhs ) );
    }

    class OrPredicate {

    PaketPredicate the_lhs;
    PaketPredicate the_rhs;

    OrPredicate ( PaketPredicate const & lhs,
    PaketPredicate const & rhs )
    : the_lhs ( lhs )
    , the_rhs ( rhs )
    {}

    public:

    friend
    OrPredicate operator|| ( PaketPredicate const & lhs,
    PaketPredicate const & rhs );

    bool operator() ( Paket const & p ) const {
    return ( the_lhs(p) || the_rhs(p) );
    }

    };

    OrPredicate operator|| ( PaketPredicate const & lhs,
    PaketPredicate const & rhs ) {
    return ( OrPredicate( lhs, rhs ) );
    }

    class NotPredicate {

    PaketPredicate the_lhs;

    NotPredicate ( PaketPredicate const & lhs )
    : the_lhs ( lhs )
    {}

    public:

    friend
    NotPredicate operator! ( PaketPredicate const & lhs );

    bool operator() ( Paket const & p ) const {
    return ( ! the_lhs(p) );
    }

    };

    NotPredicate operator! ( PaketPredicate const & lhs ) {
    return ( NotPredicate( lhs ) );
    }



    class ForallPredicate
    // [should use private inheritance]
    : public std::vector< PaketPredicate >
    {

    typedef std::vector< PaketPredicate > base;

    public:

    bool operator() ( Paket const & p ) const {
    for ( base::const_iterator iter = this->begin();
    iter != this->end(); ++iter ) {
    if ( ! (*iter)(p) ) {
    return ( false );
    }
    }
    return ( true );
    }

    };

    class ExistsPredicate
    // [should use private inheritance]
    : public std::vector< PaketPredicate >
    {

    typedef std::vector< PaketPredicate > base;

    public:

    bool operator() ( Paket const & p ) const {
    for ( base::const_iterator iter = this->begin();
    iter != this->end(); ++iter ) {
    if ( (*iter)(p) ) {
    return ( true );
    }
    }
    return ( false );
    }

    };


    // basic paket properties
    // ======================

    class Divisible {

    unsigned int the_modulus;

    public:

    Divisible ( unsigned int m )
    : the_modulus ( m )
    {}

    bool operator() ( Paket const & p ) const {
    return ( p % the_modulus == 0 );
    }

    };

    // sanity check
    // ============


    int main ( void ) {
    for ( unsigned int i = 0; i < 100; ++i ) {
    std::cout << i << " "
    << ((Divisible(2) && Divisible(3)) || Divisible(5))(i)
    << '\n';
    }
    std::cout << '\n';
    Divisible even ( 2 );
    Divisible five ( 5 );
    PaketPredicate ten = even && five;
    for ( unsigned int i = 0; i < 20; ++i ) {
    std::cout << i << " " << ten(i) << '\n';
    }
    std::cout << '\n';
    ForallPredicate rare;
    rare.push_back( ten );
    rare.push_back( ! Divisible( 7 ) );
    for ( unsigned int i = 60; i < 100; ++i ) {
    std::cout << i << " " << rare(i) << '\n';
    }

    }


    /*
    For actual paket filtering, you may have Predicates that
    check whether IP addresses are inside a specified range.
    */
    // E.g.:

    class DestinationIpInRange {};
    class SourcePortInRange {};

    /*
    Other predicates can then be defined in terms of these
    basic paket properties using the logic machinery. In the
    end, a filter would be just a ForallPredicate.
    */



    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Sep 17, 2007
    #6
  7. indrawati.yahya

    Barry Guest

    I think the first design, (while the second didn't give any detail)
    overlook the one important thing,
    The IP/PORT resources should be shared, not owned, we can't have every
    instance of XXFilter to own one copy,

    std::vector<some_smart_pointer<...> > as Kai-uwe mentioned else thread
    still don't fullfill this purpose

    should be
    some_smart_ptr<std::vector<...> >
     
    Barry, Sep 17, 2007
    #7
  8. Erik Wikström a écrit :
    And IMHO it is the same misunderstanding that happened during the
    interview: whether thinking in terms of C++ design or field idiom. Only
    the OP and the interviewer can tell.

    Michael
     
    Michael DOUBEZ, Sep 17, 2007
    #8
  9. That can easily be solved with the OP's design by adding a class like
    Thanks for all the replies. To be honest, the thought that filtering
    by IP address and port can correlate never crossed my mind during the
    interview. I always thought that they are independent of each other,
    as probably can be seen on my solution to the problem. Maybe it's true
    that the interviewer and I understood the problems differently, which
    explains his dissatisfaction with my answer. As Erik has mentioned, my
    oversight can easily be solved by adding a FilterByIPAndPort to my
    design. Had I done that, I might've gotten the job :p
     
    indrawati.yahya, Sep 17, 2007
    #9
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.